NOIP 2025 T4 题解

幸存者 · 2025-11-29 15:30:00 · 题解

详细揭秘如何用普及组算法解决这道题。

提供一个 O(nq) 的赛时做法。

首先考虑 L=R 的情况，显然可以用单调队列维护，这启发我们对于一般的情况也用单调队列维护。

具体地，我们先预处理出前缀和 sum_i=\sum\limits_{j=1}^ia_j，考虑依次计算出 i=1\sim n 的答案。

注意到对于右端点相同的区间，有用的左端点显然只有合法范围（r-l+1\in[L,R] 且 l\le i）内 sum_{l-1} 最小的那一个，所以维护的应该是按 r 升序、sum_r-sum_{l-1} 降序排列的单调队列。

为了方便我们在单调队列中维护一个二元对 (r,w) 代表区间，其中 w=sum_{l-1}。

考虑怎么动态维护这个东西，显然我们每次将 i 增加 1 的时候，要做以下三个操作：

• 删除 r=i-1 的二元对（如果有）
• 如果 i+R-1\le n，加入二元对 (i+R-1,sum_{i-1}) 并删除所有满足 sum_r-w\le sum_{i+R-1}-sum_{i-1} 的二元对 (r,w)（显然这一定是单调队列的一个后缀）
• 将所有满足 r-i+1\in[L,R] 且 w\ge sum_{i-1} 的二元对的 w 更新为 sum_{i-1}（同时要保持单调性，即删除更新后“无用”（不优于下一项）的元素）

前两个操作都是容易的，但第三个操作我们不能暴力修改。

我们发现对于所有 r<i+L-1 的区间，左端点都不可能再更新了。所以可以分成两个单调队列，将不能更新的放到第一个里面，还能更新的放到第二个里面（当然两个单调队列拼起来之后还要满足单调性）。

对于所有 r\ge i+L-1 的区间，它们对应的左端点的合法范围是一个 \le i 的后缀，所以右端点越小左端点的合法范围越大，当前的 sum_{l-1} 也就越小。换句话说，第二个单调队列中的 w 一定是单调不减的，所以我们更新的一定是第二个单调队列的一个后缀。

然而，这样直接暴力更新复杂度也是错的，但我们观察到第二个单调队列一定是由很多 w 相等的连续段构成的，那么我们只需要用链表维护连续段，就可以做到均摊 O(1) 合并了（因为链表合并的时候要删除“无用”元素）。这样时间复杂度就是均摊 O(nq) 的。

具体实现上，你会发现加入 (i+R-1,sum_{i-1}) 后并不需要立刻删除“无用”元素，合并完更新后 w=sum_{i-1} 的连续段后再依次删除“无用”元素即可。我赛时是用 deque 维护单调队列，手写链表，最后一个大样例 1.3s，应该不卡常。

以下是赛时代码（删去了调试内容和不必要的模板）：

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
int a[50010], sum[50010];
int calc(pii x)
{
    return sum[x.fi] - x.se;
}
int cnt, st[50010], ed[50010], w[50010], pre[50010], nxt[50010];
void merge(int x, int y)
{
    while (st[x] != ed[x] && sum[ed[x]] <= sum[st[y]]) ed[x] = pre[ed[x]];
    if (st[x] == ed[x] && sum[ed[x]] <= sum[st[y]]);
    else nxt[ed[x]] = st[y], pre[st[y]] = ed[x], st[y] = st[x];
    st[x] = ed[x] = w[x] = 0;
}
signed main()
{
    freopen("query.in", "r", stdin);
    freopen("query.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    cin >> q;
    while (q--)
    {
        for (int i = 1; i <= cnt; i++) st[i] = ed[i] = w[i] = 0;
        cnt = 0;
        for (int i = 1; i <= n; i++) pre[i] = nxt[i] = 0;
        int l, r;
        cin >> l >> r;
        deque<pii> q1;
        deque<int> q2;
        q2.push_back(++cnt);
        st[cnt] = l, ed[cnt] = l, w[cnt] = 0;
        for (int i = l + 1; i <= r; i++)
        {
            while (st[cnt] != ed[cnt] && sum[ed[cnt]] <= sum[i]) ed[cnt] = pre[ed[cnt]];
            if (st[cnt] == ed[cnt] && sum[ed[cnt]] <= sum[i]) st[cnt] = ed[cnt] = i;
            else nxt[ed[cnt]] = i, pre[i] = ed[cnt], ed[cnt] = i;
        }
        ull ans = (ull)(!q1.empty() ? calc(q1.front()) : sum[st[q2.front()]] - w[q2.front()]);
        for (int i = 2; i <= n; i++)
        {
            while (!q2.empty() && st[q2.front()] < i + l - 1)
            {
                q1.push_back({st[q2.front()], w[q2.front()]});
                if (st[q2.front()] == ed[q2.front()]) q2.pop_front();
                else st[q2.front()] = nxt[st[q2.front()]];
            }
            if (!q1.empty() && q1.front().fi < i) q1.pop_front();
            if (i + r - 1 <= n)
            {
                q2.push_back(++cnt);
                st[cnt] = ed[cnt] = i + r - 1, w[cnt] = sum[i - 1];
            }
            if (!q2.empty() && w[q2.back()] >= sum[i - 1])
            {
                int x = q2.back();
                q2.pop_back();
                while (!q2.empty() && w[q2.back()] >= sum[i - 1])
                {
                    merge(q2.back(), x);
                    q2.pop_back();
                }
                w[x] = sum[i - 1];
                while (!q2.empty() && sum[ed[q2.back()]] - w[q2.back()] <= sum[st[x]] - w[x])
                {
                    int y = q2.back();
                    while (st[y] != ed[y] && sum[ed[y]] - w[y] <= sum[st[x]] - w[x]) ed[y] = pre[ed[y]];
                    if (st[y] == ed[y] && sum[ed[y]] - w[y] <= sum[st[x]] - w[x]) q2.pop_back();
                }
                q2.push_back(x);
            }
            while (!q1.empty() && !q2.empty() && calc(q1.back()) <= sum[st[q2.front()]] - w[q2.front()]) q1.pop_back();
            ans ^= (ull)i * (ull)(!q1.empty() ? calc(q1.front()) : sum[st[q2.front()]] - w[q2.front()]);
        }
        cout << ans << '\n';
    }
    return 0;
}