array

#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