未开O2；

已开O2；

代码如下：

#include "bits/stdc++.h"
using namespace std;
#define Long long long int
#define MAXN 41000000
#define MAXM 101000

int N,Type,X,Y,Z,M,Now,L[MAXM],R[MAXM];
Long B[MAXN],P[MAXN],Sum[MAXN];
int Q[MAXN],Last[MAXN],H,T;

inline Long SumLine(int X){
	return ((Sum[X]<<1)-Sum[Last[X]]);
}

inline void Print(__int128 Num){
	if(Num>9)Print(Num/10);
	putchar(Num%10+'0');
	return;
}

int main(void){
	scanf("%d%d",&N,&Type);
	if(Type==0){
		for(register int i=1;i<=N;i++)
			scanf("%lld",&Sum[i]),Sum[i]=Sum[i]+Sum[i-1];
	}else if(Type==1){
		scanf("%d%d%d",&X,&Y,&Z);
		scanf("%lld%lld%d",&B[1],&B[2],&M);
		for(int i=1;i<=M;i++)
			scanf("%lld%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);
		Now=1;
		for(int i=1;i<=N;i++){
			if(i>P[Now])Now++;
			Sum[i]=Sum[i-1]+(B[i]%(R[Now]-L[Now]+1))+L[Now];
		}
	}
	
	H=1,T=1;
	for(register int i=1;i<=N;i++){
		while(H<T&&Sum[i]>=SumLine(Q[H+1]))
			H++;
		Last[i]=Q[H];
		while(H<T&&SumLine(i)<=SumLine(Q[T]))
			T--;
		Q[++T]=i;
	}
	
	__int128 AC=0;
#define Tot (Sum[This]-Sum[Last[This]])
	for(register int This=N;This;This=Last[This])
		AC=AC+((__int128)(Tot))*Tot;
	Print(AC);
	return 0;
}