80pts NOIP T4 求调教

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = -0x3f3f3f3f3f3f3f3f;
inline int read(){
	int k = 0,f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		k = k * 10 + c - '0';
		c = getchar();
	}
	return k * f;
}
inline void write(unsigned int x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x < 10) putchar(x + '0');
	else{
		write(x / 10);
		putchar(x % 10 + '0');
	}
}
int n,a[50005],pre[50005],ans[50005],ql,qr;
struct ST{
    int maxx[25][50005],st[50005];
    inline void init(){
        st[1] = 0;
        for(int i = 2;i <= n;i++) st[i] = st[i / 2] + 1;
        for(int j = 1,k = 1;j <= st[n];j++){
            for(int i = 1;i + (1 << j) - 1 <= n;i++) maxx[j][i] = max(maxx[j - 1][i],maxx[j - 1][i + k]);
            k <<= 1;
        }
    }
    inline int query(int l,int r){
        int len = r - l + 1;
        return max(maxx[st[len]][l],maxx[st[len]][r - (1 << st[len]) + 1]);
    }
}st1,st2;
inline void solve(int l,int r){
    if(l == r){
        if(ql <= 1 && qr >= 1) ans[l] = max(ans[l],a[l]);
        return;
    }
    int mid = (l + r) >> 1;
    solve(l,mid);
    solve(mid + 1,r);
    int maxx = INF;
    for(int i = l;i <= mid;i++){
        int tl = max(mid + 1,i + ql - 1),tr = min(n,i + qr - 1);
        if(tl <= tr) maxx = max(maxx,-pre[i - 1] + st1.query(tl,tr));
        if(maxx != INF) ans[i] = max(ans[i],maxx);
    }
    maxx = INF;
    for(int i = r;i > mid;i--){
        int tl = max(l,i - qr + 1),tr = min(mid,i - ql + 1);
        if(tl <= tr) maxx = max(maxx,pre[i] + st2.query(tl,tr));
        if(maxx != INF) ans[i] = max(ans[i],maxx);
    }
}
signed main(){
    n = read();
    for(int i = 1;i <= n;i++){
        a[i] = read();
        pre[i] = pre[i - 1] + a[i];
    }
    for(int i = 1;i <= n;i++){
        st1.maxx[0][i] = pre[i];
        st2.maxx[0][i] = -pre[i - 1];
    }
    st1.init();
    st2.init();
    int q = read();
    while(q--){
    	ql = read();
    	qr = read();
        fill(ans + 1,ans + n + 1,INF);
        solve(1,n);
        unsigned int c = 0;
        for(int i = 1;i <= n;i++) c ^= i * ans[i];
        write(c);
        puts("");
    }
    return 0;
}