[CSP-S2019] 划分 题解
STUDENT00
·
·
个人记录
1.前置芝士
合并神犇： https://www.luogu.com.cn/problem/P2300
题意大概就是有n个数，让你用尽量少的次数进行合并操作，每次合并相邻二数，最终使数列变成一个不下降的序列。
建议先做“合并神犇”，否则很难看懂本篇博客。
2.发掘思路
此题其实和前置芝士中的“合并神犇”十分相似，一样是要使序列单调不减，只是此处多了一点要求：最小化每个块中的数的总和的平方和。又由于：
也就是两个数越接近越好，那么“合并神犇”的dp做法不正满足了这个条件吗？所以其实这个条件是多余的。
# 3.具体实现
So easy，直接将“合并神犇”搬过来，改改输入输出，加个统计答案，就OK了。但是！这题卡空间，非常卡，所以得把a,b,sum合并成一个数组。
# 4.代码
```cpp
#include<bits/stdc++.h>
#define N 40000005
using namespace std;
const int mod=(1<<30);
int n,type,last[N],q[N],head=0,tail=1;
long long sum[N],pre[N];
__int128 ans;
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)){x=x*10+c-48;c=getchar();}
return x;
}
void printt(__int128 x){
if(x){
printt(x/10);
putchar(x%10+48);
}
}
void print(__int128 x){
if(x) printt(x);
else putchar(48);
}
signed main(){
n=read();type=read();
if(!type) for(int i=1;i<=n;i++) sum[i]=read();
else{
int x=read(),y=read(),z=read();sum[1]=read();sum[2]=read();int m=read(),p,l,r,last=1;
for(int i=3;i<=n;i++) sum[i]=(x*sum[i-1]+(long long)y*sum[i-2]+z)%mod;
while(m--){
p=read();l=read();r=read();
for(;last<=p;last++) sum[last]=sum[last]%(r-l+1)+l;
}
}
for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
for(int i=1;i<=n;i++){
while(head+1<tail&&pre[q[head+1]]+sum[q[head+1]]<=sum[i]) head++;
last[i]=q[head];pre[i]=sum[i]-sum[q[head]];
while(head<tail&&sum[q[tail-1]]+pre[q[tail-1]]>sum[i]+pre[i]) tail--;
q[tail++]=i;
}
int t=n;
while(t){
ans+=(__int128)pre[t]*pre[t];
t=last[t];
}
print(ans);
return 0;
}
```