当前位置：首页 > news >正文

题解：P14638 [NOIP2025] 序列询问

news 2026/6/5 10:26:53

前言

本文同步自洛谷专栏，题目传送门。

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

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

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

分析

特殊情况

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

首先构建两个 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})$。

$\red{\text{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 longint 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 的区间，答案为前后缀 maxfor(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];//赋值，可以不用写清空//分割线，上面在枚举右端点。下面的部分中，注意枚举左端点时，前缀和数组下标 -1for(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]$。

$[\frac{R+1}{2},R]$ 为特殊情况，容易解决。

$[L,\frac{R}{2}]$ 若应用特殊情况的算法，求解包含整块的情况时复杂度错误。

考虑特殊处理，可以利用这样一个特点：

对于一个块 $[l,r]$，若用 $[l+L-1,l+R-1]$ 中的最大值减去 $[r-R,r-L]$ 中的最小值，所得结果一定包括长度为 $[L,R]$ 的情况，

但是会错误地求解长度为 $l+R-1-(r-R)=2\times R-(r-l+1)\le 2\times R-1$。

$\red{\text{注}}$

$r-l+1$ 未必是 $L$，因为在最后一块处情况特殊。（代码实现时也要注意！）

但是在此处却不影响整体答案，问题得以解决。

时间复杂度 $O(nq)$，空间 $O(n\log{n})$。

$\red{\text{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 longint n,q;
ll ans[N],w[N],maxn[20][N],minn[20][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 pmax(ll x,ll y){return x<y?y:x;}
inline ll pmin(ll x,ll y){return x>y?y:x;}inline ll get_mi(int l,int r){int d=LG(r-l+1);return pmin(minn[d][l],minn[d][r-(1<<d)+1]);
}inline ll get_mx(int l,int r){int d=LG(r-l+1);return pmax(maxn[d][l],maxn[d][r-(1<<d)+1]);
}void calc(int L,int R,int o){//每次处理一个长为 l 的区间，答案为前后缀 max，R<=2Lfor(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++) cmax(ans[i],w[i]);//分割线，上面在枚举右端点。下面的部分中，注意枚举左端点时，前缀和数组下标 -1for(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]);}if(o==0) return;for(int l=1,r=L;l<=r;l+=L,r=min(r+L,n)){//统计包含这个块的答案ll ret=inf;for(int i=r+1;i<=n;i++){//<=n 的限制要加入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);}
}void solve(int L,int R){//此处 R*2 <= 原来 Rfor(int l=1,r=L;l<=r;l+=L,r=min(r+L,n)){//特别注意最后一块可能长度不足，r-L 不能写 l-1ll ret=get_mx(r,min(n,l+R-1))-get_mi(max(0,r-R),r-L);for(int i=l;i<=r;i++) cmax(ans[i],ret);}
}void init(){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]=pmax(maxn[i-1][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]=pmin(minn[i-1][j],minn[i-1][j+(1<<i-1)]);}}
}int main(){// freopen("query.in","r",stdin);// freopen("query.out","w",stdout);n=read(),init(),q=read();for(int id=1,l,r;id<=q;id++){l=read(),r=read(),tot=0;for(int i=1;i<=n;i++) ans[i]=inf;calc(max(l,(r+1)>>1),r,1);if(l<((r+1)>>1)) calc(l,r>>1,0),solve(l,r>>1);for(int i=1;i<=n;i++) tot^=(ull)(i*ans[i]);printf("%llu\n",tot);}return 0;
}