题解：P5665 [CSP-S2019] 划分

因为

(a+b)^2 \ge a^2 + b^2

，所以要尽可能多分段。

令

sum_{i,j}

表示

[i,j]

的区间和，

pre_{i}

表示

i

的前缀和。

若

sum_{a,b}+sum_{c,d} \le sum_{e,f}

，则

(sum_{a,b}+sum_{c,d})^2+{sum_{e,f}}^2 \le {sum_{a,b}}^2+(sum_{c,d}sum_{e,f})^2

，那么说明一个区间与前面合并一定优于与后面合并。

所以最后一段要尽可能的小。

设

f_i

表示前

i

个数的答案，

g_i

表示前

i

个数最优情况下划分的最后一段的左端点。

那么对于

i

，我们需要找到最大的

j

，使得

sum_{j+1,i}\ge sum_{g_j,j}

。

两边同时加

pre_{j}

，得到

pre_{i}\ge 2\times pre_{j}-pre_{{g_j}-1}

。

由于

pre_i

单调不减，所以显然可以单调队列优化。

对于任意的

x\le y

，若

2\times pre_{x}-pre_{{g_x}-1}\ge 2\times pre_{y}-pre_{{g_y}-1}

，那么无论在什么情况下

x

都不会被选择，直接踢出单调队列。

所以单调队列里的元素一定是根据

2\times pre_{i}-pre_{{g_i}-1}

单增的。

每个元素最多分别进出单调队列一次，时间复杂度

O(n)

。

CPP

int n; bool ty;
ULL pre[N];
__int128 ans;
int b[N],p[M],l[M],r[M];
int q[N],g[N];
LL calc(int p){return 2*pre[p]-pre[g[p]-1];}
void solve(){
	cin>>n>>ty;
	if(!ty){
		ULL a;
		for1(i,1,n) {rin(a); pre[i]=pre[i-1]+a;}
	}else{
		int x,y,z,m;
		cin>>x>>y>>z>>b[1]>>b[2]>>m;
		for1(i,1,m) cin>>p[i]>>l[i]>>r[i];
		for1(i,3,n) b[i]=(1ll*b[i-1]*x+1ll*b[i-2]*y+z)%mod;
		for1(i,1,m)
			for1(j,p[i-1]+1,p[i])
				pre[j]=pre[j-1]+b[j]%(r[i]-l[i]+1)+l[i];
	}
	int h=1,t=1;
	for1(i,1,n){
		while(pre[i]>=calc(q[h+1])&&h<t) h++;
		g[i]=q[h]+1;
		while(calc(i)<=calc(q[t])&&h<=t) t--;
		q[++t]=i;
	}
	int pos=n;
	while(pos){
		__int128 qwq=pre[pos]-pre[g[pos]-1];
		ans+=qwq*qwq;
		pos=g[pos]-1;
	}
	rout(ans);
	return ;
}

题解：P5665 [CSP-S2019] 划分

文章操作

相关推荐

评论

题解：P5665 [CSP-S2019] 划分