原题

大数据拍不挂但是 $WA on test 2$，调了2天，快崩溃了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],s[N],q,L,R,s1[32][N],s2[32][N],f[32][N][2],g[32][N][2];
int check1(int l,int r){
	if(l==r) return s1[0][l];
	int lg=log2(r-l+1);
	return max(s1[lg][l],s1[lg][r-(1<<lg)+1]);
}
int check2(int l,int r){
	if(l==r) return s2[0][l];
	int lg=log2(r-l+1);
	return min(s2[lg][l],s2[lg][r-(1<<lg)+1]);
}
int erfen1(int l,int r,int w){
	int mid,res=0,i=l;
	while(l<=r){
		mid=(l+r)>>1;
		if(check1(i,mid)+w>=R){
			r=mid-1;
			res=mid;
		}
		else l=mid+1;
	}
	return res;
}
int erfen2(int l,int r,int w){
	int mid,res=0,i=l;
	while(l<=r){
		mid=(l+r)>>1;
		if(check2(i,mid)+w<=L){
			r=mid-1;
			res=mid;
		}
		else l=mid+1;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>L>>R;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		s1[0][i]=s2[0][i]=s[i];
	}
	for(int i=1;i<=20;i++){
		for(int j=1;j<=n-(1<<(i-1))+1;j++){
			s1[i][j]=max(s1[i-1][j],s1[i-1][j+(1<<(i-1))]);
			s2[i][j]=min(s2[i-1][j],s2[i-1][j+(1<<(i-1))]);
		}
	}
	for(int i=1;i<n;i++){
		int x=erfen1(i+1,n,R-s[i]),y=erfen2(i+1,n,R-s[i]);
		if((x<y&&x)||!y){
			f[0][i][0]=x;
			g[0][i][0]=0;
		}
		else{
			f[0][i][0]=y;
			g[0][i][0]=1;
		}
		x=erfen1(i+1,n,L-s[i]),y=erfen2(i+1,n,L-s[i]);
		if((x<y&&x)||!y){
			f[0][i][1]=x;
			g[0][i][1]=0;
		}
		else{
			f[0][i][1]=y;
			g[0][i][1]=1;
		}
	}
	for(int i=1;i<=30;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<=1;k++){
				g[i][j][k]=g[i-1][f[i-1][j][k]][g[i-1][j][k]];
				f[i][j][k]=f[i-1][f[i-1][j][k]][g[i-1][j][k]];
			}
		}
	}
	cin>>q;
	while(q--){
		int b,e,w;
		cin>>b>>e>>w;
		w=max(L,min(R,w));
		int x=erfen1(b,e,w-s[b-1]),y=erfen2(b,e,w-s[b-1]);
		if(x==0&&y==0){
			cout<<w+s[e]-s[b-1]<<'\n';
			continue;
		}
		int flag;
		if(x==0) b=y,flag=1;
		else if(y==0) b=x,flag=0;
		else b=min(x,y),flag=b==x?0:1;
		int flag1=flag;
		flag=-1;
		for(int i=30;i>=0;i--){
			if(flag==-1&&f[i][b][flag1]&&f[i][b][flag1]<=e) flag=g[i][b][flag1];
			if(flag!=-1&&f[i][b][flag1]&&f[i][b][flag1]<=e){
				int bb=b;
				b=f[i][bb][flag1];
				flag1=g[i][bb][flag1];
			}
		}
		if(b==e) b--;
		if(flag1==0){
			cout<<min(R,max(R+s[e]-s[b],L))<<'\n'; 
			continue;
		}
		else{
			cout<<min(R,max(L+s[e]-s[b],L))<<'\n';
			continue;
		}
	}
}