暴力dp，用f[i][j]表示前i个数，最后一个区间是(j,i]的最小答案，转移方程用可以用前缀和来优化，复杂度为$o(n^3)$
（然后可以各种优化到$o(n^2)$，但这不需要）
输出f[i][j]，可以发现若f[i][j-1]和f[i][j]合法，那么$f[i][j]le f[i][j-1]$
证明：数归，考虑令f[i][j]和f[i][j-1]都合法，设f[i][j-1]由f[j-1][k]转移，f[i][j]由f[i][k']转移，必然有$kle k'$，即在左边可以删掉若干个数（可以为0个）来保证合法
按照这样的策略划分f[i][j-1]，设划分出的区间和分别是$S1le S2le ……le St$，然后分别在左边删除Li，右边加入Ri，显然有$L1=Rt=0$且$R_{i-1}=Li$，那么区间和从$sum_{i=1}^{t}Si^{2}$变成$sum_{i=1}^{t}(Si+Ri-Li)^2=sum_{i=1}^{t}Si^2+sum_{i=1}^{t}(Ri-R_{i-1})^{2}+2sum_{i=1}^{t}Si(Ri-R_{i-1})le sum_{i=1}^{t}Si^2+2sum_{i=1}^{t}Ri(Si-S_{i-1})le sum_{i=1}^{t}Si^2$
通过证明，同时也可以得到最优方案如何构造，用优先队列来维护出最后一个合法的，然后从n往前选择即可
考场上需要写高精度（比较懒就用__int128了）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mod (1<<30) 4 #define N 40000007 5 #define ll long long 6 #define lll __int128 7 int n,type,m,x,y,z,q[N],f[N],b[N]; 8 ll ans,a[N]; 9 ll calc(int k){ 10 return 2*a[k]-a[f[k]]; 11 } 12 void write(lll k){ 13 if (k>9)write(k/10); 14 putchar(k%10+'0'); 15 } 16 int main(){ 17 scanf("%d%d",&n,&type); 18 if (!type) 19 for(int i=1;i<=n;i++){ 20 scanf("%d",&x); 21 a[i]=a[i-1]+x; 22 } 23 else{ 24 scanf("%d%d%d%d%d%d",&x,&y,&z,&b[1],&b[2],&m); 25 for(int i=3;i<=n;i++)b[i]=(1LL*x*b[i-1]+1LL*y*b[i-2]+z)%mod; 26 int xx=1; 27 for(int i=1;i<=m;i++){ 28 scanf("%d%d%d",&x,&y,&z); 29 for(int j=xx;j<=x;j++)a[j]=a[j-1]+b[j]%(z-y+1)+y; 30 xx=x+1; 31 } 32 } 33 x=1; 34 y=0; 35 for(int i=1;i<=n;i++){ 36 while ((x<=y)&&(calc(q[x])<=a[i]))x++; 37 f[i]=q[x-1]; 38 while ((x<=y)&&(calc(q[y])>=calc(i)))y--; 39 q[++y]=i; 40 } 41 lll ans=0,o=1; 42 for(int i=n;i;i=f[i])ans+=o*(a[i]-a[f[i]])*(a[i]-a[f[i]]); 43 write(ans); 44 }