RT，23过了（1022MB卡过去的），2425MLE了

#include<iostream> 
#include<cstdio>
#define ll __int128
using namespace std;
int inline read()
{
	int ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		ans=ans*10+ch-'0';
		ch=getchar();
	}
	return ans*f;
}
void write(ll x)
{
	if(x/10)
	write(x/10);
	putchar((x%10)+'0');
}
const int mod=1<<30,N=4e7+5,M=1e5+5;
ll s[N];
int p[M],l[M],r[M],b[N],f[N];
int n,m,x,y,z,op,h,t;
void get0()
{
	for(int i=1;i<=n;i++) s[i]=s[i-1]+read();
}
void get1()
{
	x=read(),y=read(),z=read(),b[1]=read(),b[2]=read(),m=read();
	for(int i=1;i<=m;i++)
	p[i]=read(),l[i]=read(),r[i]=read();
	for(int i=3;i<=n;i++)
	b[i]=((1ll*x*b[i-1]+1ll*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++)
	s[i]=s[i-1]+(b[i]%(r[j]-l[j]+1)+l[j]);
}
ll val(int x){return s[x]*2-s[f[x]];}
int q[N];
int main()
{
	n=read();op=read();
	if(op==0) get0();
	else get1();
	h=1,t=1;
	q[t]=0;
	for(int i=1;i<=n;i++)
	{
		while(h<t&&val(q[h+1])<=s[i]) h++;
		f[i]=q[h];
		while(h<=t&&val(q[t])>=val(i)) t--;
		q[++t]=i;
	}
	ll ans=0;
	for(int i=n;i;i=f[i])
	ans+=(s[i]-s[f[i]])*(s[i]-s[f[i]]);
	write(ans);
	return 0;
}