先考虑暴力，设 $dp(i,j)$ 表示最后一段分割在区间 $[i,j)$ 上，那么最暴力的就是 $O(n^3)$ 枚举，我们发现 $dp(j,k) \to dp(i,j)$ 对于每一个 $j$ 可选的 $k$ 集应该是不断增大的，于是我们可以对于每一个 $j$ 单调队列，复杂度 $O(n^2)$。

其实我们可以配合贪心通过一些数学性质来解决这个问题或者打表，就像方差那题一样。对于这题显然越大的数，平方越大，也就是 $(a+b)^2 \ge a^2+b^2$，于是我们需要保证最后一段划分尽可能小，也就是这么多段尽可能接近或者说划分更多段。

于是我们设出 $f_i$ 表示前 $i$ 个数的答案，$g_i$ 表示最后一段划分的和。这样只需要每次找到最大的 $j$ 满足 $sum_{j+1,i} \ge g_j$ 进行转移即可。即 $pre_i \ge g_j+pre_j$，相同变量在一侧，单调队列即可。注意 $g_i$ 不一定大于 $g_{i-1}$，只是要求大于前一段并不是大于上一个位置。

时间复杂度 $O(n)$。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=4e7+10;
const int maxm=1e5+10;
const int mod=(1<<30);
long long pre[maxn],g[maxn]; int top=0;
int q[maxn],p[maxm],l[maxm],r[maxm],b[maxn],a[60];
inline long long calc(int x){ return 2*pre[x]-pre[g[x]]; }
inline long long val(int x){ return pre[x]-pre[g[x]]; }
void print(__int128 ans){
	while(ans){
		a[++top]=ans%10;
		ans/=10;
	}
	while(top) cout<<a[top--];
}
int main(){
	int n,type; cin>>n>>type;
	if(!type){
		pre[0]=0;
		for(int i=1;i<=n;i++){
			int x; cin>>x;
			pre[i]=pre[i-1]+x;
		}
	}else{
		int x,y,z,m;
		cin>>x>>y>>z>>b[1]>>b[2]>>m;
		for(int i=1;i<=m;i++) cin>>p[i]>>l[i]>>r[i];
		for(int i=3;i<=n;i++) b[i]=(1ll*b[i-1]*x+1ll*b[i-2]*y+z)%mod;
		for(int i=1;i<=m;i++)
			for(int j=p[i-1]+1;j<=p[i];j++){
				x=b[j]%(r[i]-l[i]+1)+l[i];
				pre[j]=pre[j-1]+x;
			}
	}
	q[0]=0; int l=1,r=1; q[1]=0;
	for(int i=1;i<=n;i++){
		while(pre[i]>=calc(q[l+1])&&l<r) l++;
		g[i]=q[l];
		while(calc(i)<=calc(q[r])&&l<=r) r--;
		q[++r]=i;
	}
	int P=n; __int128 ans=0,mul=1;
	while(P){
		mul=val(P); mul=mul*mul;
		ans=ans+mul; 
		P=g[P];
	}
	print(ans);
	return 0;
}