O(nq)分治做法求卡常

#include<iostream>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=5e4+5;
const ll INF=1e18;
int n,m;
int q[N],pos[N];
ll sum[N],ans[N],f[N],g[N][20],mx[N][20][20];

inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<48||c>57){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f==-1?-x:x;
}

ll chkmax(ll &x,ll y){ return x=max(x,y);}

void solve(int l,int r,int L,int R){
	if(r-l+1<L) return;
	int mid=(l+r)>>1;
	if(l<mid) solve(l,mid-1,L,R);
	if(r>mid) solve(mid+1,r,L,R);
	for(int i=max(l,mid-R+1);i<=min(r,mid+R-1);i++) f[i]=-INF;
	int p=max(l,mid-R+1),h=1,t=0;
	for(int i=max(mid,p+L-1);i<=min(r,p+R-1);i++){
		while(h<=t&&sum[q[t]]<=sum[i]) t--;
		q[++t]=i;
	}
	chkmax(f[p],sum[q[h]]-sum[p-1]);
	for(int i=p+1;i<=mid;i++){
		chkmax(f[i],f[i-1]);
		if(i+R-1<=r){
			while(h<=t&&sum[q[t]]<=sum[i+R-1]) t--;
			q[++t]=i+R-1;
		}
		while(h<=t&&q[h]<i+L-1) h++;
		if(h<=t) chkmax(f[i],sum[q[h]]-sum[i-1]);
	}
	p=min(mid+R-1,r),h=1,t=0;
	for(int i=min(mid-1,p-L);i>=max(l-1,p-R);i--){
		while(h<=t&&sum[q[t]]>=sum[i]) t--;
		q[++t]=i;
	}
	chkmax(f[p],sum[p]-sum[q[h]]);
	for(int i=p-1;i>=mid;i--){
		chkmax(f[i],f[i+1]);
		while(h<=t&&q[h]>i-L) h++;
		if(i-R>=l-1){
			while(h<=t&&sum[q[t]]>=sum[i-R]) t--;
			q[++t]=i-R;
		}
		if(h<=t) chkmax(f[i],sum[i]-sum[q[h]]);
	}
	for(int i=max(l,mid-R+1);i<=min(r,mid+R-1);i++) chkmax(ans[i],f[i]);
}

signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		int x=read();
		sum[i]=sum[i-1]+x;
	}
	int cnt=0;
	for(int i=1,len=1;i<=n;i+=len,len<<=1){
		for(int j=i;j<=min(i+len-1,n);j++) pos[j]=cnt;
		for(int j=1;j<=n;j++) ans[j]=-INF;
		solve(1,n,i,min(i+len-1,n));
		for(int j=1;j<=n;j++) g[j][cnt]=ans[j];
		cnt++;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<cnt;j++){
			for(int k=0;k<cnt;k++) mx[i][j][k]=-INF;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<cnt;j++){
			mx[i][j][j]=g[i][j];
			for(int k=j+1;k<cnt;k++) mx[i][j][k]=max(mx[i][j][k-1],g[i][k]); 
		}
	}
	m=read();
	while(m--){
		int l=read(),r=read();
		ull res=0;
		int p=pos[l],q=pos[r];
		if(p==q){
			for(int i=1;i<=n;i++) ans[i]=-INF;
			solve(1,n,l,r);
			for(int i=1;i<=n;i++) res^=1ull*i*ans[i]/*,cout<<ans[i]<<' '*/;
			cout/*<<endl*/<<res<<endl;
			continue;
		}
		for(int i=1;i<=n;i++) ans[i]=mx[i][p+1][q-1];
		solve(1,n,l,(1<<p+1)-1);
		solve(1,n,1<<q,r);
		for(int i=1;i<=n;i++) res^=1ull*i*ans[i]/*,cout<<ans[i]<<' '*/;
		cout/*<<endl*/<<res<<endl;
	}
	return 0;
}