著名卡空间的题目

对于我的程序：

//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int maxn=4e7+5,maxm=1e5+5; 

__int128 sum[maxn]={};
int b[maxn],p[maxm],l[maxm],r[maxm],f[maxn]={},n,type,h,t;
int q[maxn];

__int128 calc(int x) {
	return (sum[x]<<1)-sum[f[x]];
}

void output(int x) {
	if(x>9) {
		output(x/10);
	}
	cout<<(long long)(x%10);
}

signed main() {
	n=read();
	type=read();
	
	if(!type) {
		for(int i=1;i<=n;i++) {
			sum[i]=read();
			sum[i]+=sum[i-1];
		}
	}
	else {
		int x=read(),y=read(),z=read();
		b[1]=read();b[2]=read();
		int 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]%(1<<30)+1LL*y*b[i-2]%(1<<30))+1LL*z)%(1<<30);
		}
		
		int now=0;
		for(int i=1;i<=n;i++) {
			if(p[now]<i) {
				now++;
			}
			sum[i]=b[i]%(r[i]-l[i])+l[i];
			sum[i]+=sum[i-1];
		}
	}
	
	h=1,t=1;
	q[t]=0;
	for(int i=1;i<=n;i++) {
		while(h<t&&calc(q[h+1])<=sum[i]) {
			h++;
		}
		f[i]=q[h];
		while(h<=t&&calc(i)<=calc(q[t])) {
			t--;
		}
		q[++t]=i;
	}
	
	__int128 ans=0;
	for(int i=n;i;i=f[i]) {
		ans+=(sum[i]-sum[f[i]])*(sum[i]-sum[f[i]]); 
	}
	
	output(ans);
	return 0;
}

我们计算一下空间，大概是 $750MB$ 左右，此题空间 $1GB$。为什么会 RE 呢？

而且最后一个样例在本地也运行不了。