rt，换了一车写法还是过不了

本地测极限数据：

离散化：17s

动态开点：3s

找不到哪里复杂度错了，两次 query 都合并成一次了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const long long inf=1e18;
int n,m,a[N<<5],g[N],ls[N<<5],rs[N<<5],cnt,maxx;
long long f[N],s[N],P[N],delta;
// vector<long long>v;
// vector<int>used;
struct L{
	long long k,b;
}line[N];
long long calc(int id,int x)
{
	return line[id].k*x+line[id].b;
}
bool Less(int a,int b,int x)
{
	return calc(a,x)<calc(b,x);
}
void insert(int &rt,int l,int r,int id)
{
    if(!rt)rt=++cnt;
	if(!a[rt]){a[rt]=id;return;}
	int mid=l+r>>1;
	if(Less(id,a[rt],mid))swap(a[rt],id);
	if(l==r)return;
	if(Less(id,a[rt],l))insert(ls[rt],l,mid,id);
	if(Less(id,a[rt],r))insert(rs[rt],mid+1,r,id);
}
pair<long long,int> merge(pair<long long,int>a,pair<long long,int>b)
{
	if(a.first==b.first)
	{
		if(g[a.second]<g[b.second])return a;
		return b;
	}
	if(a.first<b.first)return a;
	return b;
}
pair<long long,int> query1(int rt,int l,int r,int x)
{
	if(!rt)return make_pair(inf,0);
	pair<long long,int> res=make_pair(calc(a[rt],x),a[rt]);
	int mid=l+r>>1;
	if(l==r)return res;
	if(x<=mid)res=merge(res,query1(ls[rt],l,mid,x));
	else res=merge(res,query1(rs[rt],mid+1,r,x));
	return res; 
}
bool check(long long val)
{
	for(int i=1;i<=cnt;i++)a[i]=ls[i]=rs[i]=0;
	line[0]={0,inf};
	cnt=1;
	int root=1;
	// insert(1,1,n,0);
	for(int i=1;i<=n;i++)
	{
		auto tmp=query1(1,1,maxx,s[i]);
		f[i]=tmp.first+P[i]+2*s[i]+1+val;
		g[i]=g[tmp.second]+1;
		line[i]={-2*s[i],f[i]+P[i]-2*s[i]};
		insert(root,1,maxx,i);
	}
	// cout<<cnt<<endl;
	return g[n]<=m;
}
char *p1,*p2,buf[10000005];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++)
int read(){
int x=0,f=1;char ch=nc();
while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}
while(ch>=48&&ch<=57){x=x*10+ch-48,ch=nc();}
return x*f;
}
int main()
{
	clock_t c1=clock();
#ifdef LOCAL
 	freopen("1.in","r",stdin);
 	freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
 	cin.tie(0);cout.tie(0);
	n=read(),m=read();
	for(int i=1;i<=n;i++)s[i]=read(),s[i]+=s[i-1],P[i]=s[i]*s[i],maxx=max(1ll*maxx,s[i]);
	long long l=-1e18,r=1e18;
	while(l<r)
	{
		long long mid=l+r>>1;
		// check(mid);
		if(check(mid))r=mid;
		else l=mid+1;
	}
	// delta=0;
	check(l);
	cout<<f[n]-l*m-inf;
	// query2(1,1,maxx,114514);
#ifdef LOCAL
	cerr<<"Time used:"<<clock()-c1<<"ms";
#endif
 	return 0;
}