记录编号	571532	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2019S]划分	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.287 s
提交时间	2022-05-27 20:10:43	内存使用	332.07 MiB

//CSP也有原题是真没想到
//同 [Codeforces229D]Towers
//卡常好恶心QAQ 
#include <bits/stdc++.h>
#define LL __int128
using namespace std;
const int maxn = 4e7 + 5;
const int maxm = 1e5 +5;
typedef long long ll;
LL read() {
	LL s = 0,f = 1;
	char c = getchar();
	for(;!isdigit(c);c = getchar())
		if(c == '-')f = -1;
	for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
	return s * f;
}
void write(LL x) {
	if(x < 0) {
		putchar('-');
		x = -x;
	}
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
	return ;
}
int x,y,z;
int b[maxn];
ll s[maxn];
int a[maxn],m,n,pos[maxn];
int p[maxm],l[maxm],r[maxm];
int q[maxn],head,tail;
ll SUM(int x) {
	return s[x] - s[pos[x]] + s[x];
}
void datamaker() {
	scanf("%d%d%d%d%d%d",&x,&y,&z,&b[1],&b[2],&m);
	for(int i = 1;i <= m;++ i)scanf("%d%d%d",&p[i],&l[i],&r[i]);
	for(int i = 3;i <= n;++ i)b[i] = (x * b[i - 1] + y * b[i - 2] + z) & ((1 << 30) - 1);
	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];
			s[i] = s[i - 1] + a[i]; 
		}
	}
	return ;
}
int main() {
	freopen("2019partition.in","r",stdin);
	freopen("2019partition.out","w",stdout);
	int tp;
	scanf("%d%d",&n,&tp);
	if(tp)datamaker();
	else for(int i = 1;i <= n;++ i)scanf("%d",&a[i]),s[i] = s[i - 1] + a[i];
	q[head = tail = 1] = 0;
	for(int i = 1;i <= n;++ i) {
		for(;head < tail&&SUM(q[head]) <= s[i]&&SUM(q[head + 1]) <= s[i];)q[head ++] = 0;
		pos[i] = q[head];
		for(;head < tail&&SUM(q[tail]) >= SUM(i);)q[tail --] = 0;
		q[++ tail] = i;
	}
	LL ans = 0;
	for(int cur = n;cur;cur = pos[cur])ans += ((LL)(s[cur] - s[pos[cur]]) * (s[cur] - s[pos[cur]]));
	write(ans);
	return 0;
}