记录编号	595012	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019S]划分	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.608 s
提交时间	2024-10-06 21:47:59	内存使用	92.60 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 4e7+10;
const ll inf = 1e8;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}
void write(__int128 x){
    if(x > 9)write(x / 10);
    putchar(x % 10 + '0');
}


int n,type,b[N],p[N];
ll s[N];

int l = 0,r = 1,st[N];
ll get(int i){return s[i] * 2 - s[p[i]];}
ll x,y,z,m;
int main(){
	freopen("2019partition.in","r",stdin);
	freopen("2019partition.out","w",stdout);
	n = read(),type = read();
	if(!type)for(int i = 1;i <= n;i++)s[i] = s[i-1] + read();
	else{
		x = read(),y = read(),z = read(),b[1] = read(),b[2] = read(),m = read();
		int st = 0;
		for(int i = 1;i <= m;i++){
			ll p = read(),l = read(),r = read();
			for(int j = st+1;j <= p;j++){
				if(j > 2)b[j] = ((ll)x * b[j-1] + (ll)y * b[j-2] + z) % (1<<30);
				s[j] = s[j-1] + (ll)b[j] % (r-l+1) + l;
 			}
 			st = p;
		}
	}
	int x = 0;
	for(int i = 1;i <= n;i++){
		while(l <= r && get(st[l]) <= s[i])x = max(x,st[l]),l++;
		p[i] = x;
		while(l <= r && get(st[r]) >= get(i))r--;
		st[++r] = i;
	}
	__int128 ans = 0;
	while(n)ans += (__int128)(s[n] - s[p[n]]) * (s[n] - s[p[n]]),n = p[n];
	write(ans);

	return 0;

}