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

Wxb2010 · 2025-11-30 11:12:52 · 题解

前言

参考资料：题解，作者 Doqe 大佬。

做法：具体地按 L 分块解决 R<2\times L 的情况。

当然，也可以认为我是来提供代码实现的。

分析

特殊情况

设当前询问范围为 [L,R]，采用按 L 分块解决 R<2\times L 的情况。

首先构建两个 ST 表，分别支持前缀和数组区间最小值、最大值。

::::info[关于单调队列]

部分情况下可以改为单调队列，但是 ST 表使用起来会更加方便。

::::

假设当前的分块为 [l,r]=[l,l+L)，那么，所有与此块有交的区间可以分为三种（有重合，但不影响答案）：

• 左端点在块内。

• 右端点在块内。

• 包含整块。

右端点在块内时，枚举块内的点作为右端点，利用 ST 表得出各点的答案（没有可行区间就设置为负无穷）。

然后可以发现：由于块长为 L，x 作为右端点时，所得的答案对 [l,x] 都成立，可以进行一个后缀 \max 完成统计，复杂度 O(L)。

左端点在块内时同理，注意前缀和数组的一些下标问题，统计用前缀 \max。

包含整块的情况，暴力向右枚举右端点，并规定左端点 \le l，则长度一定 \ge L，一直枚举到不存在 \le R 的情况为止，复杂度 O(R-L)=O(L)。

全局共 \frac{n}{L} 块，总复杂度就是 O(n)。

倍增预处理解决一般情况

按照值域倍增，预处理出 [2^i,2^{i+1}) 的答案，然后合并为区间，时间复杂度和空间复杂度都是 O(n\log^2{n})。

注：也可以再建一个 ST 表，但是复杂度上没有必要。

然后每次询问时，将询问拆成三部分：[L,2^x),[2^x,2^y),[2^y,R]。

其中 2^{x-1}\le L<2^x,2^y\le R<2^{y+1}。

可以解决此问题，时间复杂度 O(nq)，空间 O(n\log^2{n})。

::::info[code]

#include<bits/stdc++.h>
using namespace std;
#define gc() getchar()
#define ll long long
#define N 50005
#define inf -1000000000000000ll
#define ull unsigned long long

int n,q,u;
ll ans[N],w[N],mx[20][20][N];
ll maxn[20][N],minn[20][N],res[N];
ull tot;

inline int read(){
    int a=0,c=gc(),f=0;
    for(;!isdigit(c);c=gc()) f|=c=='-';
    for(;isdigit(c);c=gc()) a=10*a+c-'0';
    return f?-a:a;
}

inline void cmax(ll &x,ll y){(x<y)&&(x=y);}
inline void cmin(ll &x,ll y){(x>y)&&(x=y);}
inline int LG(int x){return 31^__builtin_clz(x);}

inline ll get_mi(int l,int r){
    int d=LG(r-l+1);
    return min(minn[d][l],minn[d][r-(1<<d)+1]);
}

inline ll get_mx(int l,int r){
    int d=LG(r-l+1);
    return max(maxn[d][l],maxn[d][r-(1<<d)+1]);
}

void calc(int L,int R){//每次处理一个长为 l 的区间，答案为前后缀 max
    for(int l=1,r=L;l<=r;l+=L,r=min(r+L,n)){
        for(int i=l;i<=r;i++){
            w[i]=i-L>=0?minn[0][i]-get_mi(max(0,i-R),i-L):inf;
        }
        for(int i=r-1;i>=l;i--) cmax(w[i],w[i+1]);
        for(int i=l;i<=r;i++) ans[i]=w[i];//赋值，可以不用写清空
        //分割线，上面在枚举右端点。下面的部分中，注意枚举左端点时，前缀和数组下标 -1
        for(int i=r;i>=l;i--){
            w[i]=i+L-1<=n?get_mx(i+L-1,min(n,i+R-1))-maxn[0][i-1]:inf;
        }
        for(int i=l+1;i<=r;i++) cmax(w[i],w[i-1]);
        for(int i=l;i<=r;i++) cmax(ans[i],w[i]);
        //统计包含这个块的答案
        ll ret=inf;
        for(int i=r+1;i<=n;i++){
            if(i-R>l-1) break;
            cmax(ret,minn[0][i]-get_mi(max(i-R,0),l-1));
        }
        for(int i=l;i<=r;i++) cmax(ans[i],ret);
    }
}

int main(){
    // freopen("query.in","r",stdin);
    // freopen("query.out","w",stdout);
    n=read(),u=LG(n);
    for(int i=1;i<=n;i++){
        maxn[0][i]=minn[0][i]=read()+maxn[0][i-1];
    }
    for(int i=1;i<=LG(n+1);i++){
        for(int j=0,up=n-(1<<i)+1;j<=up;j++){
            maxn[i][j]=maxn[i-1][j],cmax(maxn[i][j],maxn[i-1][j+(1<<i-1)]);
        }
    }
    for(int i=1;i<=LG(n+1);i++){
        for(int j=0,up=n-(1<<i)+1;j<=up;j++){
            minn[i][j]=minn[i-1][j],cmin(minn[i][j],minn[i-1][j+(1<<i-1)]);
        }
    }
    for(int i=0;i<=u;i++){
        for(int j=0;j<=u;j++){
            for(int k=1;k<=n;k++) mx[i][j][k]=inf;
        }
    }
    for(int i=0;i<u;i++){
        calc(1<<i,(1<<i+1)-1);
        for(int j=1;j<=n;j++) mx[i][i][j]=ans[j];
    }
    for(int l=0;l<u;l++){//直接处理每个区间
        for(int r=l+1;r<u;r++){
            for(int i=1;i<=n;i++){
                mx[l][r][i]=mx[l][r-1][i];
                cmax(mx[l][r][i],mx[r][r][i]);
            }  
        }
    }
    q=read();
    for(int id=1,l,r;id<=q;id++){
        l=read(),r=read(),tot=0;
        if(r<2*l){
            calc(l,r);
            for(int i=1;i<=n;i++) tot^=(ull)(i*ans[i]);
            printf("%llu\n",tot);continue;
        }
        int x=LG(l)+1,y=LG(r);
        for(int i=1;i<=n;i++) res[i]=mx[x][y-1][i];
        calc(l,(1<<x)-1);
        for(int i=1;i<=n;i++) cmax(res[i],ans[i]);
        calc(1<<y,r);
        for(int i=1;i<=n;i++) cmax(res[i],ans[i]);
        for(int i=1;i<=n;i++) tot^=(ull)(i*res[i]);
        printf("%llu\n",tot);
    }
    return 0;
}

::::

无需预处理的方法

为参考资料中的 bonus。

可以将询问简单拆为两部分：[L,\frac{R}{2}],[\frac{R+1}{2},R]。