★水题之路|2019CCPC网络赛 HDU6703 - array（线段树查询时剪枝）【线段树】|★数据结构|#

链接：HDU6703 - array
题意：
给出 n n n个数的数组 a 1 , a 2 , ? , a n   ( ? i ∈ [ 1 , n ] , 1 ≤ a i ≤ n ≤ 1 0 5 ) a_1,a_2,\cdots,a_n\; (?i∈[1,n],1≤a_i≤n\le10^5) a1?,a2?,?,an?(?i∈[1,n],1≤ai?≤n≤105)，其中 a a a各不相同。
【★水题之路|2019CCPC网络赛 HDU6703 - array（线段树查询时剪枝）】给出 m   ( 1 ≤ m ≤ 1 0 5 ) m\; (1≤m≤10^5) m(1≤m≤105)个操作，分为 2 2 2种：

( 1 , p o s ) (1,pos) (1,pos)，令 a p o s = a p o s + 1 0 7 a_{pos}=a_{pos}+10^7 apos?=apos?+107；
( 2 , r , k ) (2,r,k) (2,r,k)，询问不等于 a 1 , a 2 , ? , a r a_1,a_2,\cdots,a_r a1?,a2?,?,ar?中任意一个数，且 ≥ k \ge k ≥k的最小整数。

分析：
根据数组 a a a建立权值线段树，里面存储各个权值在数组 a a a的位置，由于询问的最小整数要不等于 a 1 , a 2 , ? , a r a_1,a_2,\cdots,a_r a1?,a2?,?,ar?中任意一个数，所以不等于 a a a的权值的位置应初始化为 > n \gt n >n（如 n + 1 n+1 n+1），这样就不会被排除。
查询时只需要查询权值 [ k , n ] [k,n] [k,n]中最小的且位置 > r \gt r >r的权值，如果没找到，则答案一定是 n + 1 n+1 n+1（可以想象该情况就是数组 a a a将 1 1 1~ n n n的权值恰好填满了）。
对于令 a p o s = a p o s + 1 0 7 a_{pos}=a_{pos}+10^7 apos?=apos?+107，由于 1 0 7 10^7 107足够大，则可以直接将 a p o s a_{pos} apos?删去即可（令权值 a p o s a_{pos} apos?的位置变为 > n \gt n >n）。

关键是在权值线段树中的查询操作，权值线段树记录区间中的最大位置，这样就可以判断左、右区间内存不存在最大位置 > r \gt r >r。
遍历到线段树的一个结点，若左子树存在最大位置 > r \gt r >r，则优先向左子树遍历，但是左子树不一定有答案（因为是左子树，所以位置 > r \gt r >r的权值不一定 ≥ k \ge k ≥k）；若左子树没答案，再判断右子树的是否存在最大位置 > r \gt r >r，若存在，则答案一定在右子树（因为是左子树，所以位置 > r \gt r >r的权值一定 ≥ k \ge k ≥k），若不存在，则不要遍历右子树。
那么这样剪枝后，最坏的情况也只有 O ( 2 log ? n ) O(2\log n) O(2logn)。

以下代码：

#include #define LL long long using namespace std; const int MOD=998244353; const int INF=0x3f3f3f3f; const int maxn=1e5+50; int n,m,a[maxn]; int t[maxn<<2]; void build(int rt,int l,int r) { if(l==r) { t[rt]=n+1; return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); t[rt]=max(t[rt<<1],t[rt<<1|1]); } void updata(int rt,int l,int r,int val,int pos) { if(l==r) { t[rt]=pos; return; } int mid=(l+r)>>1; if(val<=mid) updata(rt<<1,l,mid,val,pos); else updata(rt<<1|1,mid+1,r,val,pos); t[rt]=max(t[rt<<1],t[rt<<1|1]); } int query(int rt,int l,int r,int k,int lim) { if(l==r) { if(t[rt]>lim) return l; else return n+1; } int mid=(l+r)>>1; int ans=n+1; if(k<=mid&&t[rt<<1]>lim) ans=query(rt<<1,l,mid,k,lim); if(ans==n+1&&t[rt<<1|1]>lim) ans=query(rt<<1|1,mid+1,r,k,lim); return ans; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); build(1,1,n); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); updata(1,1,n,a[i],i); } int op,pos,r,k; int ans=0; while(m--) { scanf("%d",&op); if(op==1) { scanf("%d",&pos); pos^=ans; updata(1,1,n,a[pos],n+1); } else { scanf("%d %d",&r,&k); r^=ans; k^=ans; ans=query(1,1,n,k,r); printf("%d\n",ans); } } } return 0; }