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

· · 题解

绷不住了，这个题最关键的 DE 性质我赛时以为是给被卡常的正解的分没有去想，返校看了别人游记发现 DE 性质是关键，回宿舍想了一会发现秒了。。。

不过按照我过 T2 的时间（11:39）来看，就算场上注意了 DE 性质也不太能够过（写+调 1h-eps）就是了。

Solution

考虑 A 性质。将原序列按 L 分块，那么区间 ckmax 相当于对一个块的前缀与另一个块的后缀做 ckmax。容易做到 O(nq)。

考虑 D 性质。这相当于区间一定经过序列中点，我们将序列分成前后两半，同理区间 ckmax 只有块内的前后缀 ckmax。考虑快速求出前后缀 ckmax 的是什么，这相当于固定区间的其中一个端点并询问使区间和最大的另一个端点是什么，直接做一个滑动窗口即可。

考虑 E 性质。类似 D 性质，我们将序列分成四块即可，注意此时还有对整块 ckmax 的情况。

考虑正解。发现上述过程本质上是在用 O(\frac{R}{L}n) 的时间求出一组 (L,R) 的答案。考虑倍增分块，这样会分出 O(\log n) 个块，预处理块间信息并在查询时暴力计算散块信息即可。

容易做到 O(n\log^2 n+nq) 或更低。

Code

bool Mst;
#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=5e4+5,mod=998244353;
constexpr ll INF=1e18;
inline ll add(ll x,ll y){return (x+=y)>=mod&&(x-=mod),x;}
inline ll Add(ll &x,ll y){return x=add(x,y);}
inline ll sub(ll x,ll y){return (x-=y)<0&&(x+=mod),x;}
inline ll Sub(ll &x,ll y){return x=sub(x,y);}
inline ll qpow(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)res=res*a%mod;
    return res;
}
int n,m,qs,a[N];ll s[N];
ll pre[N],suf[N],val[N],tmp[16][16][N];
int q[N],l,r;
inline void work(int B,int L,int R){
    for(int i=1;i<=n;i++)pre[i]=suf[i]=-INF;
    l=0,r=-1;
    for(int i=L;i<=n;i++){
        while(l<=r&&q[l]<i-R)l++;
        while(l<=r&&s[q[r]]>=s[i-L])r--;
        q[++r]=i-L;
        pre[i]=max(pre[i],s[i]-s[q[l]]);
    }
    l=0,r=-1;
    for(int i=n-L;i>=0;i--){
        while(l<=r&&q[l]>i+R)l++;
        while(l<=r&&s[q[r]]<=s[i+L])r--;
        q[++r]=i+L;
        suf[i+1]=max(suf[i+1],s[q[l]]-s[i]);
    }
    int u=0,v=0;
    while(v<n){
        u=v+1,v=min(u+B-1,n);
        for(int i=u+1;i<=v;i++)suf[i]=max(suf[i],suf[i-1]);
        for(int i=v-1;i>=u;i--)pre[i]=max(pre[i],pre[i+1]);
        for(int i=u;i<=v;i++)val[i]=max(val[i],max(pre[i],suf[i]));
        if(u>1&&v<n){
            ll tag=-INF;
            int pu=u-B,pv=v-B,nu=u+B,nv=min(v+B,n);
            l=0,r=-1;
            for(int i=R;i>L;i--){
                while(l<=r&&s[q[r]]>=s[nu-i])r--;
                q[++r]=nu-i;
            }
            for(int i=nu;i<=nv;i++){
                while(l<=r&&q[l]<i-R)l++;
                if(i-L<=pv){
                    while(l<=r&&s[q[r]]>=s[i-L])r--;
                    q[++r]=i-L;
                }
                if(l<=r)tag=max(tag,s[i]-s[q[l]]);
            }
            for(int i=u;i<=v;i++)val[i]=max(val[i],tag);
        }
    }
}
inline void out(){
    ull res=0;
    for(int i=1;i<=n;i++)res^=(ull)i*(ull)val[i];
    cout<<res<<'\n';
}
bool Med;
int main(){
    cerr<<abs(&Mst-&Med)/1048576.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n,m=__lg(n);
    for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
    for(int i=m;i>=0;i--){
        for(int i=1;i<=n;i++)val[i]=-INF;
        work(1<<i,1<<i,min((1<<(i+1))-1,n));
        for(int k=1;k<=n;k++)
            tmp[i][i][k]=val[k];
        for(int j=i+1;j<=m;j++)
            for(int k=1;k<=n;k++)
                tmp[i][j][k]=max(tmp[i][j-1][k],tmp[i+1][j][k]);
    }
    cin>>qs;
    while(qs--){
        int l,r;cin>>l>>r;
        for(int i=1;i<=n;i++)val[i]=-INF;
        int x=__lg(l),y=__lg(r);
        if(x==y)
            work(1<<x,l,r);
        else{
            work(1<<x,l,(1<<(x+1))-1);
            work(1<<y,1<<y,r);
            if(x+1<=y-1){
                for(int i=1;i<=n;i++)
                    val[i]=max(val[i],tmp[x+1][y-1][i]);
            }
        }
        out();
    }
    return 0;
}