Description
Link.
给出一个数列，要求将其分成几段，使每段的和非严格递增，求最小的每段的和的平方和。
Solution
注意到 (a_{i}) 为正，对于正数有这样的结论：
[a^{2}+b^{2}<(a+b)^{2}
]
正确性显然。这告诉我们，分的段越多越好。
现在我们来考虑如何使每段的和非严格递增。
考虑暴力 DP，设 (f_{i,j}) 为前 (i) 个数然后上一个 breakpoint 是 (j) 的最小平方和，转移：
[f_{i,j}=min_{1le k<j,pre_{i}-pre_{j}ge pre_{j}-pre_{k}}{f_{j,k}+(pre_{i}-pre_{j})^{2}}
]
(pre) 为前缀和。当然这个 DP 什么结论都没用，没有任何技术含量。
所以我们考虑优化。
你会发现这个 (k) 不是每次都要重头枚举，他是单调的，于是你维护 (f_{j,k}) 最小值即可，复杂度变成了 (mathcal{O}(n^{2}))。
考虑上面的结论，你会发现我们只需要找打第一个可行的转移点 (k) 即可。
意味着我们可以维护一个 (g_{i}) 来表示：前 (i) 个数，我们最大的一个合法 (k)。这个东西肯定是单调不降的。
转移即：
[g_{i}=max_{pre_{i}-pre{j}ge pre_{j}-pre_{g_{j}}}{j}
]
变形得：
[g_{i}=max_{pre_{i}ge pre_{j} imes2-pre_{g_{j}}}{j}
]
显然判定条件的右边有单调性（(pre_{j}+(pre_{j}-pre_{g_{j}}))），左边也有单调性。
然后单调队列优化即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 _LL;
int n,a[40000010],taskID,f[40000010],que[40000010],head,tail;
LL pre[40000010];
_LL ans;
template<typename T>
void read(T &hhh)
{
T x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=getchar();
if(~f) hhh=x;
else hhh=-x;
}
template<typename T>
void write(T x,char las='
')
{
static int stk[100],top=0,f=0;
if(x<0) x=-x,f=1;
do stk[++top]=x%10,x/=10; while(x);
if(f) putchar('-');
while(top) putchar(stk[top--]^'0');
putchar(las);
}
void generateData(int taskID)
{
if(taskID) for(int i=1;i<=n;++i) read(a[i]);
else
{
static int p[100010],l[100010],r[100010],b[40000010];
LL x,y,z;
int m;
read(x),read(y),read(z),read(b[1]),read(b[2]),read(m);
const int MOD=(1<<30);
for(int i=1;i<=m;++i) read(p[i]),read(l[i]),read(r[i]);
for(int i=3;i<=n;++i) b[i]=(LL(x)*b[i-1]%MOD+LL(y)*b[i-2]%MOD+z)%MOD;
for(int j=1;j<=m;++j)
{
for(int i=p[j-1]+1;i<=p[j];++i) a[i]=(b[i]%(r[j]-l[j]+1))+l[j];
}
}
for(int i=1;i<=n;++i) pre[i]=pre[i-1]+a[i];
}
int main()
{
read(n),read(taskID);
generateData(taskID^1);
for(int i=1;i<=n;++i)
{
while(head<tail&&pre[i]>=(pre[que[head+1]]<<1)-pre[f[que[head+1]]]) ++head;
f[i]=que[head];
while(head<tail&&(pre[i]<<1)-pre[f[i]]<=(pre[que[tail]]<<1)-pre[f[que[tail]]]) --tail;
que[++tail]=i;
}
for(int i=n;i;i=f[i]) ans+=_LL(pre[i]-pre[f[i]])*(pre[i]-pre[f[i]]);
write(ans);
return 0;
}