#include <bits/stdc++.h> using namespace std; const int N=1e5+5; const int inf=2e9; struct vv{ int l,r,id; }tree[N<<2]; int a[N]; void build(int l,int r,int p) { tree[p].l=l;tree[p].r=r; if(tree[p].l==tree[p].r) { tree[p].id=0; return; } int mid=(tree[p].l+tree[p].r)>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1); tree[p].id=0; } void modify(int pos,int val,int p)//更新区间最大下标. { int mid=(tree[p].l+tree[p].r)>>1; if(tree[p].l==tree[p].r) { tree[p].id=val; return; } if(pos<=mid) { modify(pos,val,p<<1); } else { modify(pos,val,p<<1|1); } tree[p].id=max(tree[p<<1].id,tree[p<<1|1].id); } int query(int l,int r,int k,int u)//在树下标l,r中找到大于等于k最小的数,当前节点是u { if(tree[u].l==tree[u].r) { if(tree[u].id>k) return l; else return inf; } if(tree[u].id<=k) return inf; int mid=(tree[u].l+tree[u].r)>>1; int idl=tree[u<<1].id,idr=tree[u<<1|1].id; if(r<=mid)//递归左边. { if(idl<=k) return inf; return query(l,r,k,u<<1); } if(l>mid)//递归右边. { if(idr<=k) return inf; return query(l,r,k,u<<1|1); } int ans,ans1,ans2; ans=ans1=ans2=inf; //还有一种两边都有的情况. if(idl>k) ans1=query(l,mid,k,u<<1); if(idr>k&&ans1==inf) ans2=query(mid+1,r,k,u<<1|1); ans=min(ans1,ans2); return ans; } int main() { int T; scanf("%d",&T); while(T--) { int n,m,ans=0; scanf("%d%d",&n,&m); build(1,n,1); for(int i=1;i<=n;i++) { int x;scanf("%d",&x); a[i]=x; modify(x,i,1); } while(m--) { int op; scanf("%d",&op); if(op==1) { int pos; scanf("%d",&pos); pos^=ans; modify(a[pos],inf,1); } else { int r,k; scanf("%d%d",&r,&k); r^=ans;k^=ans; ans=query(k,n,r,1); if(ans==inf) ans=n+1; printf("%d\n",ans); } } } return 0; }
思路就是线段树的下标维护权值,线段树维护区间id的max,再进行递归找合法值,然后可以进行一下剪枝,就是左边找到了右边就不用找了...因为线段树暂时没做几个题,所以显得有些不熟练2333