太空飞船

Description
环上有 N 个整数 \(l_i\)。要把环划分成 K 段，使得每段之和的方差最小。

HINT
三个部分:

1. \(K=2,N\leq10^5\).
2. \(K=3,N\leq3\times10^5\).
3. \(K\leq20,N\leq400\).

Solution
第一部分直接枚举一个断点,另一个断点三分即可.

第二部分将环复制两遍,直接枚举一个断点,另外两个断点肯定是在总和的三分点附近.

第三部分比较麻烦.

把方差的式子展开发现,其实只需最小化每段之和的平方的和.

\(f[i][j]\) 表示前 \(j\) 个数分成 \(i\) 段的最小值.

\(f[i][j]=min\{f[i-1][k]+(s[j]-s[k])^2\}\).

撇开 \(i\) 那一维考虑一下斜率优化.

如果 \(k1>k2\) 且 \(f[j]_{k_1} 的情况:

\(f[k_1]+(s[j]-s[k_1])^2

\(f[k_1]+s[j]^2-2\times s[j]\times s[k_1]+s[k_1]^2

\(f[k_1]+s[k_1]^2-f[k_2]-s[k_2]^2<2\times s[j]\times(s[k_1]-s[k_2])\)

\(\frac{f[k_1]+s[k_1]^2-f[k_2]-s[k_2]^2}{s[k_1]-s[k_2]}<2\times s[j]\)

考虑队列中的情况:

如果当前比其优的,后面也一定比其优;如果当前比其劣的,后面有可能比其优.

按 \(\frac{f[k_1]+s[k_1]^2-f[k_2]-s[k_2]^2}{s[k_1]-s[k_2]}\) 维护上升序列,每次操作前弹出劣的队头,取队头为 \(k\).

#define K 21
#define M 401
#define N 600001
using namespace std;
ll f[K][M],ans,inf; 
int l[N],s[N],q[N],n,k,h,t;
inline ll sqr(int x){
	return 1ll*x*x;
}
inline ll g(int x){
	return k*sqr(x)-2ll*s[n]*x;
}
inline ll G(int x,int i){
	return f[i-1][x]+sqr(s[x]);
}
inline void Aireen(){
	n=read();k=read();
	for(int i=1;i<=n;++i) s[i]=l[i]=read();
	for(int i=1;i<=n;++i) s[i]+=s[i-1];
	if(k==2){
		for(int i=1;i>1;
			if(yi&&s[y-1]-s[j]>=z) --y;
			ans=min(ans,sqr(s[j]-s[i])+sqr(s[y]-s[j])+sqr(s[r]-s[y]));
			if(y-1>i)ans=min(ans,sqr(s[j]-s[i])+sqr(s[y-1]-s[j])+sqr(s[r]-s[y-1]));
			if(y+1i)ans=min(ans,sqr(s[j+1]-s[i])+sqr(s[y-1]-s[j+1])+sqr(s[r]-s[y-1]));
				if(yi){
				ans=min(ans,sqr(s[j-1]-s[i])+sqr(s[y]-s[j-1])+sqr(s[r]-s[y]));
				if(y-1>i)ans=min(ans,sqr(s[j-1]-s[i])+sqr(s[y-1]-s[j-1])+sqr(s[r]-s[y-1]));
				if(y+1

#define N 200005
#define INF 1000000001
struct Splay{
	int c[2],f,mx,mi,di,li,ri,siz,val;
}tr[N];
int e[N],n,m,rt,cnt;
inline void recnt(int u){
	int lef=tr[u].c[0],rig=tr[u].c[1];
	tr[u].siz=tr[lef].siz+tr[rig].siz+1;
	tr[u].mx=tr[u].mi=tr[u].val;tr[u].di=INF;
	if(!lef) tr[u].li=tr[u].val; 
	else{
		tr[u].mx=max(tr[lef].mx,tr[u].mx);
		tr[u].mi=min(tr[lef].mi,tr[u].mi);
		tr[u].li=tr[lef].li;
		tr[u].di=min(tr[lef].di,tr[u].di);
		tr[u].di=min(tr[u].di,abs(tr[lef].ri-tr[u].val));
	}
	if(!rig) tr[u].ri=tr[u].val; 
	else{
		tr[u].mx=max(tr[u].mx,tr[rig].mx);
		tr[u].mi=min(tr[u].mi,tr[rig].mi);
		tr[u].ri=tr[rig].ri;
		tr[u].di=min(tr[u].di,tr[rig].di);
		tr[u].di=min(tr[u].di,abs(tr[u].val-tr[rig].li));
	}
}
inline void build(int l,int r,int f){
	int mid=(l+r)>>1;
	if(l>1;build(1,cnt,0);
	char c[10];int x,y;
	while(m--){
		scanf("%s",&c);x=read();y=read();
		if(c[1]=='a')/*max*/mx(x+1,y+1);
		else if(c[1]=='i')/*min*/mi(x+1,y+1);
		else if(c[1]=='e')/*merge*/merge(x+1,y);
		else/*insert*/insert(x+1,y); 
	}
}