记录编号	616249	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2025 T4]序列询问	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	29.389 s
提交时间	2026-06-03 08:15:10	内存使用	82.65 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 5e4 + 10;
const ll inf = 1e12;
ll mx[17][N], mn[17][N], s[N], ans[N], G[17][17][N], f[N], g[N];
int n, m, logn[N], d, q[N], h, t, a[N], bl[17], br[17], pos[N], numb;
int qmax(int l, int r) {
    d = logn[r - l + 1];
    return max(mx[d][l], mx[d][r - (1 << d) + 1]);
}
int qmin(int l, int r) {
    d = logn[r - l + 1];
    return min(mn[d][l], mn[d][r - (1 << d) + 1]);
}
void solve(int l, int r) {
    fill(f + 1, f + 1 + n, -inf);
    fill(g + 1, g + 1 + n, -inf);
    int L, R;
    for (int i = 1; i <= n; i++) {
        L = i + l - 1, R = min(n, i + r - 1);
        if (L <= R) {
            f[i] = qmax(L, R) - s[i - 1];
        }
    }
    for (int i = n; i >= 1; i--) {
        L = max(i - r, 0), R = i - l;
        if (L <= R) {
            g[i] = s[i] - qmin(L, R);
        }
    }
    h = 1, t = 0;
    for (int i = 1; i <= n; i++) {
        while (h <= t && i - q[h] >= l) {
            h++;
        }
        while (h <= t && f[q[t]] <= f[i]) {
            t--;
        }
        q[++t] = i;
        ans[i] = max(ans[i], f[q[h]]);
    }
    h = 1, t = 0;
    for (int i = n; i >= 1; i--) {
        while (h <= t && q[h] - i >= l) {
            h++;
        }
        while (h <= t && g[q[t]] <= g[i]) {
            t--;
        }
        q[++t] = i;
        ans[i] = max(ans[i], g[q[h]]);
    }
    return;
}
int main() {
	freopen("query.in", "r", stdin);
	freopen("query.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        s[i] = s[i - 1] + a[i];
    }
    for (int i = 0; i <= n; i++) {
        mx[0][i] = mn[0][i] = s[i];
    }
    logn[0] = -1;
    for (int i = 1; i <= n + 1; i++) {
        logn[i] = logn[i / 2] + 1;
    }
    for (int i = 1; i <= 16; i++) {
        for (int j = 0; j + (1 << i) - 1 <= n; j++) {
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
        }
    }
    for (int k = 0;; k++) {
        bl[k] = (1 << k);
        br[k] = min(n, (1 << (k + 1)) - 1);
        for (int j = bl[k]; j <= br[k]; j++) {
            pos[j] = k;
        }
        fill(ans + 1, ans + 1 + n, -inf);
        solve(bl[k], br[k]);
        for (int j = 1; j <= n; j++) {
            G[k][k][j] = ans[j];
        }
        if (br[k] == n) {
            break;
        } else {
            numb = k;
        }
    }

    for (int x = 1; x <= n; x++) {
        for (int i = numb; i >= 0; i--) {
            for (int j = 0; j <= numb; j++) {
                if (i == j) {
                    continue;
                }
                G[i][j][x] = max(G[i + 1][j][x], G[i][j - 1][x]);
            }
        }
    }
    scanf("%d", &m);
    int ql, qr, bL, bR;
    while (m--) {
        scanf("%d %d", &ql, &qr);
        fill(ans + 1, ans + 1 + n, -inf);
        bL = pos[ql], bR = pos[qr];
        if (bL == bR) {
            solve(ql, qr);
        } else {
            solve(ql, br[bL]);
            solve(bl[bR], qr);
            if (bL < bR - 1) {
                bL++, bR--;
                for (int j = 1; j <= n; j++) {
                    ans[j] = max(ans[j], G[bL][bR][j]);
                }
            }
        }
        ull res = 0;
        for (int i = 1; i <= n; i++) {
            res ^= 1ull * i * ans[i];
        }
        printf("%llu\n", res);
    }
    return 0;
}