题解：P14638 [NOIP2025] 序列询问 / query（民间数据）

王熙文 · 2025-11-30 11:10:30 · 题解

思路

注意到 q 远小于 n，而我们想得到 \mathcal O(nq) 的做法，那么肯定需要对 q 个区间进行离散化。接下来，我们希望求出 ans_{i,j} 表示包含 i、长度在第 j 个离散化区间中的区间的总和最大值。如果求出这个数组，查询就变成了 n 次给出长度为 q 的数组并进行 q 次区间 RMQ 查询，这个问题是容易解决的。

设求出来的离散化数组 lsh 表示 [lsh_i,lsh_{i+1}-1] 是第 i 个离散化区间。

枚举区间的左端点 l 和离散化区间 j，此时我们希望将所有 r \in [r_1=i+lsh_j-1,r_2=i+lsh_{j+1}-2] 的区间总和贡献到 i \in [l,r] 的 ans_{i,j}。然而 r 是变化的。于是这个做法最有思维含量的地方就在这里了：考虑只贡献到 [l,r_1]，这样的话只需要求出所有 r\in [r_1,r_2] 的区间总和 \max 再对 [l,r_1] 进行区间取 \max 即可。

那 [r_1+1,r] 之间漏掉的贡献怎么办？枚举右端点再做一遍！枚举 r，求出 l_1=r-lsh_j+1,l_2=r-lsh_{j+1}+2，那么一定有 l \in [l_2,l_1]，此时可以将 [l,r] 这个区间的答案覆盖到 [l_2,r]。如果 l_2 \le r_1+1，那么 [l,r_1] 与 [l_2,r] 就可以完全覆盖 [l,r] 了。

那什么条件下才有 l_2 \le r_1+1 呢？只需要满足 r-l_2+1 \ge r-r_1 即可。前者就是 lsh_j，后者最大值便是 r_2-r_1=lsh_{j+1}-lsh_j，那么条件转化为 lsh_j \ge lsh_{j+1}-lsh_j。这启示我们在 lsh 数组中再加入一些元素，使得 lsh 的后一项不超过前一项的两倍。这是容易的，从前到后枚举，对于 lsh_i，若有 2lsh_i<lsh_{i+1} 则加入 2lsh_i。因为加入的元素满足相邻元素至少相差两倍，所以加入的个数是 \mathcal O(\log n) 的。这样处理之后，就可以使用我们之前的做法了。

回顾之前的做法，我们需要求出 r \in [r_1,r_2] 时 sum(l,r) 的最大值，转化为前缀和相减后使用 st 表即可。接下来需要将答案贡献到 [l,r_1]。考虑先枚举离散化区间 j，再枚举左端点，则每个答案贡献到的区间长度均为 lsh_j。那么可以将答案放到 l 上，对于某个 i，只需要查询 [i-lsh_j+1,i] 之间的答案最大值即可，而这个问题可以使用单调队列解决。

当我们求出 ans_{i,j} 后，问题即转化为对有 n 个长度为 q 的数组，q 次分别求出 n 个数组中固定的一段区间的最大值。存在 \mathcal O(n)-\mathcal O(1) RMQ 但是我不会，于是考场编了一个离线 \mathcal O(nq) 的做法。

考虑对 q 次询问离线，枚举询问区间的右端点 r，对 n 个数组维护单调栈。对于在 r 出的一个询问，正常做法是在单调栈上二分 \ge l 的第一个位置 x。但是在多个数组下，可以将 n 个问题同时做，直接枚举这个位置。将 n 个单调栈上的值都放到对应的位置上，我们希望枚举 x 位置上的值时它们恰好都是其所在单调栈上 \ge l 的第一个位置。于是将每个值的上一个位置 pre 从小到大排序，则可以取的便是一段前缀。这样可以做到一个右端点 \mathcal O(n+q) 的复杂度。

考虑移动右端点时如何维护这样的结构。注意到单调栈的增加只会在 i 处同时加入 n 个 i 位置的值，剩下的便只有删除。因此可以对每个位置上排序后的序列维护链表，链表可以支持删除、遍历前缀。加入 n 个 i 位置的值时因为值域只有 \mathcal O(q)，所以可以桶排序。这样就做完了。

综上，这个做法理论复杂度是 \mathcal O(n(q+\log n))。

实际上我考场调完第一部分（求出 ans_{i,j}）后已经 12:40 了，完全没时间实现第二部分，于是我索性直接用 st 表处理第二部分，竟然跑得飞快，最后一个大样例仅用了 1.5s。奇怪的是，倒数第二个大样例竟然用了 4s，但是复杂度瓶颈却是在第一部分。所以第二部分用 st 表直接维护应该可以跑过，问题仅仅出在第一部分常数太大。

还有一个问题是 ans_{i,j} 储存不下来，于是只能对 i 分成若干段（我取的是 B=3 段）分别求。

代码

拼尽全力卡常还是在洛谷卡不进去，最慢的点 2.07s，就算过了吧。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
int n,a[50010]; int qzh[50010];
int st[20][50010];
inline int query(int l,int r)
{
    return max(st[__lg(r-l+1)][l],st[__lg(r-l+1)][r-(1<<__lg(r-l+1))+1]);
}
int sst[20][50010];
inline int qquery(int l,int r)
{
    return min(sst[__lg(r-l+1)][l],sst[__lg(r-l+1)][r-(1<<__lg(r-l+1))+1]);
}
int m,l[2110],r[2110],ll[2110],rr[2110];
int tot=0,lsh[2110];
int ttot=0,gt[2110];
int ans[2110][50010];
int now[50010];
int bg,ed,q[50010];
ull sum[1050];
int stt[12][2110];
inline int queryy(int l,int r)
{
    return max(stt[__lg(r-l+1)][l],stt[__lg(r-l+1)][r-(1<<__lg(r-l+1))+1]);
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i],qzh[i]=qzh[i-1]+a[i],st[0][i]=sst[0][i]=qzh[i];
    for(int i=1; i<=17; ++i)
    {
        for(int j=0; j<=n-(1<<i)+1; ++j)
        {
            st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
            sst[i][j]=min(sst[i-1][j],sst[i-1][j+(1<<i-1)]);
        }
    }
    cin>>m;
    for(int i=1; i<=m; ++i) cin>>l[i]>>r[i],lsh[++tot]=l[i],lsh[++tot]=r[i]+1;
    sort(lsh+1,lsh+tot+1),tot=unique(lsh+1,lsh+tot+1)-lsh-1;
    gt[ttot=1]=1;
    for(int i=1; i<=tot; ++i)
    {
        while(gt[ttot]*2<lsh[i]) ++ttot,gt[ttot]=gt[ttot-1]*2;
        if(gt[ttot]!=lsh[i]) gt[++ttot]=lsh[i];
    }
    tot=ttot,memcpy(lsh,gt,sizeof(gt));
    int ax=0;
    for(int i=1; i<=m; ++i)
    {
        ll[i]=lower_bound(lsh+1,lsh+tot+1,l[i])-lsh;
        rr[i]=lower_bound(lsh+1,lsh+tot+1,r[i]+1)-lsh-1;
        ax=max(ax,__lg(rr[i]-ll[i]+1));
    }
    int B=(n+1-1)/1;
    for(int L=1,R; L<=n; L=R+1)
    {
        R=min(L+B-1,n);
        memset(ans,-0x3f,sizeof(ans));
        for(int j=1; j<=tot-1; ++j)
        {
            bg=1,ed=0;
            for(int i=max(L-lsh[j]+1,1); i<=R; ++i)
            {
                int r1=i+lsh[j]-1,r2=min(i+lsh[j+1]-2,n);
                if(r1<=n)
                {
                    now[i]=query(r1,r2)-qzh[i-1];
                    while(ed>=bg && now[q[ed]]<=now[i]) --ed;
                    q[++ed]=i;
                }
                if(i>=L)
                {
                    while(bg<=ed && q[bg]<i-lsh[j]+1) ++bg;
                    ans[j][i-L]=max(ans[j][i-L],now[q[bg]]);
                }
            }
            bg=1,ed=0;
            for(int i=min(R+lsh[j]-1,n); i>=L; --i)
            {
                int r1=i-lsh[j]+1,r2=max(i-lsh[j+1]+2,1);
                if(r1>=1)
                {
                    now[i]=qzh[i]-qquery(r2-1,r1-1);
                    while(ed>=bg && now[q[ed]]<=now[i]) --ed;
                    q[++ed]=i;
                }
                if(i<=R)
                {
                    while(bg<=ed && q[bg]>i+lsh[j]-1) ++bg;
                    ans[j][i-L]=max(ans[j][i-L],now[q[bg]]);
                }
            }
        }
        for(int j=L; j<=R; ++j)
        {
            for(int k=1; k<=tot; ++k) stt[0][k]=ans[k][j-L];
            for(int k=1; k<=ax; ++k)
            {
                for(int l=1; l<=tot-(1<<k)+1; ++l)
                {
                    stt[k][l]=max(stt[k-1][l],stt[k-1][l+(1<<k-1)]);
                }
            }
            for(int i=1; i<=m; ++i) sum[i]^=(ull)j*queryy(ll[i],rr[i]);
        }
    }
    for(int i=1; i<=m; ++i) cout<<sum[i]<<'\n';
    return 0;
}