题解「Luogu5665 划分」
转载注明来源：https://www.cnblogs.com/syc233/p/13663639.html
丧心病狂卡时空题
题意
给你一个长为 (n) 的数列 ({a_n}) ，需要找到若干个分界点 (1 leq k_1 <k_2 <k_3<cdots<k_p < n) ，满足：
[sum_{i=1}^{k_1} a_i leq sum_{i=k_1+1}^{k_2}a_i leq cdotsleq sum_{i=k_p+1}^na_i
]
同时最小化：
[(sum_{i=1}^{k_1} a_i)^2 + (sum_{i=k_1+1}^{k_2}a_i)^2 + cdots + (sum_{i=k_p+1}^na_i)^2
]
题解
容易想到一个 (O(n^2)) 的DP：令 (f_i) 表示划分 (1 sim i) 的最小答案， (g_i) 表示答案取到 (f_i) 时上一段的末尾， (s_i) 为 ({a_n}) 的前缀和。则有：
[f_i=min_{0leq j <i}{f_j+(s_i-s_j)^2|(s_j-s_{g_j})leq(s_i-s_j)}
]
更新 (f_i) 时顺带更新下 (g_i) 。
这样能拿到 (64pt) 。
注意到这样一个性质：最后一段的和越小，答案越优。
那么有：
[egin{aligned}
g_i&=max pos s.t. (s_i-s_{pos})geq(s_{pos}-s_{g_{pos}})\
&=max pos s.t. s_igeq(2 cdot s_{pos}-s_{g_{pos}})\
end{aligned}
]
令 ({ m{val}}(i)=2cdot s_i-s_{g_i}) ，则：
[g_i=max pos s.t. s_igeq{
m{val}}(pos)
]
因为 (s_i) 是递增的，所以若存在 (a,b) ，满足 (a<b<i,{ m{val}}(a)>{ m{val}}(b)) ，那么 (a) 能够转移时， (b) 一定能够转移，那 (a) 必定不会成为最优解。于是可以用单调队列来求出 (g_i) 。
由于这题时空都卡得比较死，所以最后用 (g_i) 来求出答案。
( ext{Code}:)
#include <cstring>
#include <cstdio>
#define maxn 40000005
#define maxm 100005
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
template <typename T>
inline void read(T &x)
{
x=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}
void write(__int128 x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,type,a[maxn],p[maxm],L[maxm],R[maxm];
lxl sum[maxn];
int q[maxn],l,r;
inline void make()
{
int m;lxl x,y,z,bpp,bp,bn;
lxl mod=1<<30;
read(x),read(y),read(z),read(bpp),read(bp),read(m);
for(int i=1;i<=m;++i) read(p[i]),read(L[i]),read(R[i]);
for(int j=1;j<=m;++j)
{
for(int i=p[j-1]+1;i<=p[j];++i)
{
if(i==1) bn=bpp;
else if(i==2) bn=bp;
else bn=(x*bp+y*bpp+z)%mod;
a[i]=bn%(R[j]-L[j]+1)+L[j];
if(i>=3) bpp=bp,bp=bn;
}
}
}
int pre[maxn];
int main()
{
// freopen("P5665.in","r",stdin);
read(n),read(type);
if(!type) for(int i=1;i<=n;++i) read(a[i]);
else make();
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+a[i];
l=1,r=0;
for(int i=1;i<=n;++i)
{
while(l<=r&&2*sum[q[l]]-sum[pre[q[l]]]<=sum[i]) ++l;
pre[i]=q[l-1];
while(l<=r&&2*sum[q[r]]-sum[pre[q[r]]]>=2*sum[i]-sum[pre[i]]) --r;
q[++r]=i;
}
__int128 ans=0;
int now=n;
while(now)
{
ans+=((__int128)sum[now]-sum[pre[now]])*(sum[now]-sum[pre[now]]);
now=pre[now];
}
write(ans);
return 0;
}