思路与算法

记前缀和 $S[0]=0$，区间 $[p+1,r]$ 的权值为 $S[r]-S[p]$。对一次长度限制 $[L,R]$，扫描需要被覆盖的位置 $i$。此时可用起点前缀为 $p<i$，它给终点区间 $[p+L,p+R]$ 提供常数 $-S[p]$。令 $F(r)$ 是所有已加入起点提供的最大常数，那么答案就是 $\max_{r\ge i}(S[r]+F(r))$。

先用单调栈预处理每个 $p$ 左侧最近的严格更小前缀位置 $j$。加入 $p$ 时，已有更小前缀中最靠右的是 $j$，它能支配到终点 $j+R$；其后，所有仍覆盖终点的旧前缀值都不小于 $S[p]$。所以这次区间取最大值恰能化为后缀赋值：把 $[\max(p+L,j+R+1),\min(n,p+R)]$ 的 $F$ 设为 $-S[p]$；没有 $j$ 时只用 $p+L$。

用双端队列保存 $F$ 的分段常数块。后缀赋值从队尾弹出被覆盖块，必要时裁短最后一个块，再添加新块；删除 $r<i$ 的终点从队首弹出并裁剪。一个块 $[l,r]$ 的得分是其常数加 $\max S[l\ldots r]$，用静态ST表常数时间取得。

还需取得全部块的最大得分。程序以两个带栈内最大值的栈模拟双端队列；某端空时，把另一端按一半拆分后重建。这样支持两端插入、删除和整体取最大值的均摊常数时间。扫描得到每个位置最大和后，使用无符号64位乘法和异或，自动实现题意的模 $2^{64}$。

正确性说明

在扫描位置 $i$ 时，已加入的起点前缀恰为 $0\ldots i-1$；对每个终点 $r\ge i$，提供贡献的起点还满足 $L\le r-p\le R$，这与“合法长度且覆盖 $i$”完全等价。因此若正确维护 $F$，其与 $S[r]$ 的总最大值就是所求。

考虑新起点 $p$。所有更早起点的左覆盖端点均不大于 $p+L$。若存在较小前缀，其最大的下标为 $j$，那么在新覆盖范围内直至 $j+R$ 都有一个更优旧贡献，新起点无需修改；而在 $j+R$ 之后，任何较小前缀都已结束覆盖，其他旧贡献至多等于 $-S[p]$，故应被该常数覆盖。新覆盖右端点又只会比此前总右端增加至多1。这证明实际变化恰是所给后缀赋值。

分段队列的弹块、裁剪和追加精确实现这次赋值；删去过期终点也只改变队首。每块得分通过静态最值精确求出，双栈保存的最大值与全部块最大值相等。所以每步得到正确覆盖最优值。最后无符号转换、乘法的截断和异或等价于题目指定的非负64位模结果。

复杂度

前缀和、最近更小位置和对数表初始化 $O(n)$；ST表初始化 $O(n\log n)$ 时间、空间。每询问至多加入 $n$ 个块；被赋值弹出的块、过期弹出的块各至多线性次，每步至多额外裁剪两端各一块。双栈队列一端耗尽时按半分重建，重建后需要与规模成比例的端点操作才可能再次对同量元素重建，故聚合成本为线性。一次询问 $O(n)$，总时间 $O(n\log n+nq)$，空间 $O(n\log n)$。

易错点

最近位置要求前缀和严格更小，单调栈应弹出大于等于当前值的项。不要只维护每个终点的最佳区间再向左右传播，最佳区间可能不覆盖当前点。裁剪块后必须重新查询块内最大前缀和。长度端点均闭合。最大区间和可能为负，先转无符号再相乘才能得到题目规定的模，而非有符号溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Block {
    int l, r;
    ll add, score;
};
struct MaxDeque {
    struct Item {
        Block block;
        ll mx;
    };
    vector<Item> a, b;
    vector<Block> temporary;
    static void push(vector<Item> &v, Block x) {
        v.push_back({x, max(x.score, v.empty() ? LLONG_MIN : v.back().mx)});
    }
    void balance(bool front) {
        temporary.clear();
        for (int i = (int)a.size() - 1; i >= 0; i--)
            temporary.push_back(a[i].block);
        for (auto &x : b)
            temporary.push_back(x.block);
        int n = temporary.size(), cut = front ? (n + 1) / 2 : n / 2;
        a.clear();
        b.clear();
        for (int i = cut - 1; i >= 0; i--)
            push(a, temporary[i]);
        for (int i = cut; i < n; i++)
            push(b, temporary[i]);
    }
    bool empty() const {
        return a.empty() && b.empty();
    }
    Block front() {
        if (a.empty())
            balance(true);
        return a.back().block;
    }
    Block back() {
        if (b.empty())
            balance(false);
        return b.back().block;
    }
    void pop_front() {
        if (a.empty())
            balance(true);
        a.pop_back();
    }
    void pop_back() {
        if (b.empty())
            balance(false);
        b.pop_back();
    }
    void push_front(Block x) {
        push(a, x);
    }
    void push_back(Block x) {
        push(b, x);
    }
    ll maximum() const {
        return max(a.empty() ? LLONG_MIN : a.back().mx, b.empty() ? LLONG_MIN : b.back().mx);
    }
    void clear() {
        a.clear();
        b.clear();
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> S(n + 1);
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        S[i] = S[i - 1] + x;
    }
    vector<int> previous(n), stack;
    for (int p = 0; p < n; p++) {
        while (!stack.empty() && S[stack.back()] >= S[p])
            stack.pop_back();
        previous[p] = stack.empty() ? -1 : stack.back();
        stack.push_back(p);
    }
    vector<int> lg(n + 1);
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    vector<vector<ll>> rmq(lg[n] + 1, vector<ll>(n + 1));
    rmq[0] = S;
    for (int z = 1; z < (int)rmq.size(); z++)
        for (int i = 1; i + (1 << z) - 1 <= n; i++)
            rmq[z][i] = max(rmq[z - 1][i], rmq[z - 1][i + (1 << (z - 1))]);
    auto rangeMax = [&](int l, int r) {
        int z = lg[r - l + 1];
        return max(rmq[z][l], rmq[z][r - (1 << z) + 1]);
    };
    MaxDeque deque;
    deque.a.reserve(n);
    deque.b.reserve(n);
    deque.temporary.reserve(n);
    int q;
    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        deque.clear();
        uint64_t answer = 0;
        for (int i = 1; i <= n; i++) {
            int p = i - 1, right = min(n, p + R),
                left = max(p + L, previous[p] < 0 ? 0 : previous[p] + R + 1);
            if (left <= right) {
                while (!deque.empty() && deque.back().l >= left)
                    deque.pop_back();
                if (!deque.empty()) {
                    Block x = deque.back();
                    if (x.r >= left) {
                        deque.pop_back();
                        x.r = left - 1;
                        x.score = x.add + rangeMax(x.l, x.r);
                        deque.push_back(x);
                    }
                }
                deque.push_back({left, right, -S[p], -S[p] + rangeMax(left, right)});
            }
            while (!deque.empty() && deque.front().r < i)
                deque.pop_front();
            Block x = deque.front();
            if (x.l < i) {
                deque.pop_front();
                x.l = i;
                x.score = x.add + rangeMax(x.l, x.r);
                deque.push_front(x);
            }
            answer ^= (uint64_t)i * (uint64_t)deque.maximum();
        }
        cout << answer << '\n';
    }
}