本文共 5494 字，大约阅读时间需要 18 分钟。

题目

骗分思路：动态规划

暴力的方法

枚举每个划分点。$\mathcal{O}($应该过不了$)$ 。

动态规划

用 $f(x,y)$ 表示最后一段是 $(x,y]$ ，将前 $y$ 个数完成划分的总花费最小值。

那么 $$f(x,y)=\underset{z=0}{\overset{x-1}{\min }}f(z,x)\left[\sum _{r=x+1}^y{a}_r\ge \sum _{r=z+1}^x{a}_r\right]$$

直接这样实现，复杂度就会是 $\mathcal{O}(n^3)$ 。

真·动态规划

将 $x$ 固定，$y$ 在不断右移的过程中，$z$ 的取值范围会逐渐左移。移动的同时取 $\min$ 值即可。

void solve(){   	for(int i=0; i<=n; ++i)		for(int j=0; j<=n; ++j)			dp[i][j] = infty;	dp[0][0] = 0;	for(int i=0; i<=n; ++i){   		long long sigmaJ = 0, sigmaK = 0;		int k = i; long long minK = dp[i][i];		for(int j=i+1; j<=n; ++j){   			sigmaJ += a[j];			while(k and sigmaK+a[k] <= sigmaJ){   				sigma += a[k];				minK = min(minK,dp[-- k][i]);			}			dp[i][j] = minK+sigmaJ*sigmaJ;		}	}}

正解：圣·动态规划

多充几包升个星马上就过了

使用神奇结论——最后一段越小越好。

该怎么证明呢？ 打表发现 我还是写个可能比较严谨的证明吧。

使用数学归纳法。将此条件记为性质 $P$ 。

对于右端点为 $1$ 的情况，显然成立（毕竟左端点只能是 $1$ ）。

倘若右端点严格小于 $k$ 的情况都已经满足性质 $P$ ；对于右端点为 $k$ 的情况，考虑两种不同的划分，满足：最后一段是指定的，其余是最优。

先证明几个小的结论。

均匀原理

如果 $a+b=c+d$ 且 $|a-b|<|c-d|$，那么 $a^2+b^2<c^2+d^2$ 。也就是说，和一定，差越小越好。

证明

考虑 $a,b$ 和 $a-x,b+x$ （假设 $0\le x\le a\le b$ ）。

直接暴力计算右边那一组的贡献，为 $(a-x{)}^2+(b+x{)}^2=a^2+b^2+2x(x+b-a)$ 。

由于 $0\le x\le a\le b$ ，所以 $2x(x+b-a)>0$ ，所以右边那一组的代价更高。而显然右边那一组中，两个数的差更大。

不包含原理

如果两个划分出来的区间 $[l_1,r_1],[l_2,r_2]$ 满足 $r_1\le r_2<k$ ，那么 $l_1\le l_2$ 。

证明

由于右端点小于 $k$ 的点，都已经满足性质 $P$ ，所以将红色的区间移动成蓝色的区间更优。因为一定有解（剩下的直接抄袭上面的方案）。与假设矛盾。

最后的最小

然后考虑两个不同的方案，谁会更优。

想想，要是我们把 $Red$ 的区间缩小为 $Blue$ 的区间，$Black$ 的区间就会变大为 $Pink$ 的区间。

原本 $Red$ 的区间，长度是比 $Black$ 的区间小的，根据 均匀原理 ，代价总和会变大。将这种“方案”记为方案三。——尽管这可能并不是合法的方案。

即使是这样，由于右端点小于 $k$ 的区间已经满足性质 $P$（别忘了我们是数学归纳法！），显然 $x<k$ ，而 $Blue$ 的区间比 $Green$ 的区间更小，所以：上面的方案，比方案三的代价更大！

但是，方案三比方案二还要差，所以 上面的方案劣于下面的方案！

代码优化

知道这个性质，如何优化我们的 $\mathtt{D}\mathtt{P}$ 呢？

谁说的可以不用动态规划了扔出去喂鱼

这说明我们代码中

minK = min(minK,dp[-- k][i]);

这一行鸟用没有！因为找到的第一个，就会是 $\min$ 。

更准确地说，如果 $f(y,x)$ 可以往后转移， $y$ 一定是某个只与 $x$ 有关的值！那么我们存辣么多状态做什麼？

用 $g(x)$ 表示那个 只与x有关的值 ，记 $s_x={\sum }_{i=1}^x{a}_i$ ，那么可以从 $y$ 转移到 $x$ 的充要条件是 $s_x-s_y\ge s_y-s_{g(y)}$ 即 $s_x\ge 2s_y-s_{g(y)}$ 。

$y$ 越大越优，因为本质上 $g(x)=y$ 。而且 $s_x$ 是递增的！可以直接套 单调队列。

对了，$f$ 值好像不用存？因为 $g(x)$ 已经全权代表了 $f$ 。最后求答案的时候，直接模拟一遍。

代码

关于大整数的部分，可以直接用两个长整型接在一起。

对于带取模的 $\mathtt{l}\mathtt{o}\mathtt{n}\mathtt{g}\mathtt{l}\mathtt{o}\mathtt{n}\mathtt{g}$ 相乘，可以看。或者你一个__int128立刻完事儿。

#include 
   
    #include 
    
     #include 
     
      using namespace std;inline int readint(){   	int a = 0, f = 1; char c = getchar();	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -1;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}class BigInteger{    // 坑爹的大整数 // 答案在__int128范围内（即两个long long接在一起） 	const static long long Mod = (long long)1e18;	long long head, tail;public:	BigInteger(long long num = 0){   		head = 0, tail = num;	}	BigInteger operator=(const long long num){   		return *this = BigInteger(num);	}	BigInteger &operator+=(const BigInteger &that){   		tail += that.tail;		head += that.head;		if(tail >= Mod)			++ head, tail -= Mod;		return *this;	}	BigInteger sqr()const{    // when head equals to 0		BigInteger ppl; // result		ppl.head = (long long)((long double)tail/Mod*tail);		ppl.tail = (tail*tail-ppl.head*Mod+Mod)%Mod;		return ppl;	}	void output(){   		if(head){   			printf("%lld",head);			printf("%018lld",tail);		}		else			printf("%lld",tail);	}};const int MaxN = 40000000;long long s[MaxN+1]; int n;int b[MaxN+1];void input(){   	n = readint(); int T = readint();	if(not T){   		for(int i=1; i<=n; ++i)			s[i] = s[i-1]+readint();		return ;	}	long long x = readint(), y = readint(), z = readint();	b[1] = readint(), b[2] = readint(); int m = readint();	const int Mod = (1<<30)-1;	for(int i=3; i<=n; ++i)		b[i] = (1ll*b[i-2]*y+1ll*b[i-1]*x+z)&Mod;	for(int i=1,lastp=0,p,L,R; i<=m; ++i,lastp=p){   		p = readint(), L = readint(), R = readint();		for(int j=lastp+1; j<=p; ++j)			s[j] = s[j-1]+(b[j]%(R-L+1))+L;	}}const int Mod = (1<<20)-1;// 在luogu题解中看到的循环队列优化 int q[Mod+1], head, tail, g[MaxN+1];# define pre(x) (((x)-1)&Mod)# define suf(x) (((x)+1)&Mod)# define val(x) (2*s[(x)]-s[g[(x)]])void solve(){   	head = 0, tail = 0; // [head,tail) 	for(int i=1,now=0; i<=n; ++i){   		while(head != tail and val(q[head]) <= s[i])			now = q[head], head = suf(head);		g[i] = now; // now记录可行解（最大的一个） 		while(head != tail and val(q[pre(tail)]) >= val(i))			tail = pre(tail); // 单调队列		q[tail] = i, tail = suf(tail);	}	BigInteger ans = 0;	for(int i=n; i; i=g[i]){   // printf("divide at: %d\n",i);		BigInteger t = s[i]-s[g[i]];		ans += t.sqr();	}	ans.output(); putchar('\n');}int main(){   	input(), solve();	return 0;}