数据范围较小时，可以考虑 dp。设 \(f(i,j)\) 表示当前段末尾为 \(i\)，上一段末尾为 \(j\) 的最小代价。转移为：
\[f(i,j)= \min _{s_i-s_j \ge s_j-s_k}f(j,k)+(s_i-s_j)^2
\]
时间复杂度 \(O(n^3)\)。
不难想到一个性质：要使得 \(f(i,j)\) 最小，上一段末尾 \(j\) 要尽可能靠后。这样就能保证 \((s_i-s_j)^2\) 每次都比较小。
有了这个贪心结论，重新定义 dp 状态，省去第二维。假如现在有决策点 \(j\)，要求划分合法，则需要 \(s_i-s_j\ge pre(j)\)，\(pre(j)\) 表示上一段末尾为 \(j\) 的总和。移项，\(s_j+pre(j) \le s_i\)。
不难发现，\(s_j+pre(j)\) 满足单调性，因此可以二分 \(j\)，或者直接使用单调队列。
注意：本题内存紧张，需要尽可能地省去无用的数组，比如说，\(f(n)\) 其实可以倒推得到。同时注意 __int128。
// Title: 划分
// Source: CSP-S2019
// Author: Jerrywang
#include <bits/stdc++.h>
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define LL __int128
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=40000001;
using namespace std;
inline void write(LL x)
{
if(x<10)
{
putchar(x+48); return;
}
write(x/10), putchar(x%10+48);
}
int n, type, b[N], q[N], pre[N], hh, tt;
ll a[N];
inline ll d(int i) {return a[i]-a[pre[i]];}
int main()
{
scanf("%d%d", &n, &type);
if(type==0)
{
rep(i, 1, n) scanf("%lld", a+i), a[i]+=a[i-1];
}
else
{
int x, y, z, m; scanf("%d%d%d", &x, &y, &z);
scanf("%d%d%d", b+1, b+2, &m);
rep(i, 3, n)
b[i]=((ll)x*b[i-1]+(ll)y*b[i-2]+z)%(1<<30);
int p1=0;
while(m--)
{
int p, l, r; scanf("%d%d%d", &p, &l, &r);
rep(i, p1+1, p) a[i]=b[i]%(r-l+1)+l, a[i]+=a[i-1];
p1=p;
}
}
rep(i, 1, n)
{
int j;
// s[i]-s[q[hh]]>=d[q[hh]]
while(hh<=tt && a[q[hh]]+d(q[hh])<=a[i])
j=q[hh++];
pre[i]=j;
while(hh<=tt && a[q[tt]]+d(q[tt])>=a[i]+d(i)) tt--;
q[++tt]=i;
}
LL res=0; int i=n;
while(i) res+=(LL)d(i)*d(i), i=pre[i];
write(res);
return 0;
}