array

这是一道权值线段树。根据题目给出的条件可以得出所求的值最大也就是n+1，所以$a_{pos}+10000000$只需要把值调到n+1就可以了。先对a数组按照本身的值进行排序，这样可以寻找到>=k的最小值，线段树维护的值是每个数的下标，根据下标以及上面>=k的最小值就可以求出答案了。

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
typedef long double lf;
typedef pair<int,int>P;
typedef unsigned long long ul;
const int inf = 0x3f;
const int N = 6e5+10;
const ll mod = 2012;
const double PI = 3.14;
const ul base = 131;

int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int random(int n){return(ll)rand()*rand()%n;}


int a[N],b[N];
int tree[N<<4];

void build(int rt,int left,int right){
    if(left == right){
        tree[rt] = b[left];
        return;
    }
    int mid = (left+right)/2;
    build(2*rt,left,mid);
    build(2*rt+1,mid+1,right);
    tree[rt] = max(tree[2*rt],tree[2*rt+1]);
}
void query(int rt,int left,int right,int l,int r,int c,int &ans){
    if(right < l || left > r) return;
    if(ans != -1) return;
    if(left == right && left >= l && right <= r){
        ans = left;
        return;
    }
    int mid = (left+right)/2;
    if(tree[2*rt] > c) query(2*rt,left,mid,l,r,c,ans);
    if(tree[2*rt+1] > c) query(2*rt+1,mid+1,right,l,r,c,ans);
}
void update(int rt,int left,int right,int k,int c){
    if(left == right){
        tree[rt] = c;
        return;
    }
    int mid = (left+right)/2;
    if(k <= mid) update(2*rt,left,mid,k,c);
    else update(2*rt+1,mid+1,right,k,c);
    tree[rt] = max(tree[2*rt],tree[2*rt+1]);
}
void solve(){
    int n = read(),m = read();
    for(int i = 1;i <= n;i++){
        a[i] = read();
        b[a[i]] = i;
    }
    build(1,1,n);
    int LastAns = 0;
    while(m--){
        int op = read();
        if(op == 2){
            int r = read(),k = read();
            r ^= LastAns;
            k ^= LastAns;
          //  cout<<r<<" "<<k<<endl;
        //    cout<<k<<" "<<r<<endl;
            int ans = -1;
            query(1,1,n,k,n,r,ans);
            if(ans == -1) ans = n+1;
            LastAns = ans;
            cout<<ans<<endl;
        }else {
            int pos = read();
            pos ^= LastAns;
            //cout<<pos<<endl;
            if(a[pos] != n+1){
                int x = a[pos];
                a[pos] = n+1;
              //  cout<<x<<endl;
                update(1,1,n,x,n+1);
            }
            /*
            for(int i = 1;i <= 9;i++){
                printf("%3d",tree[i]);
            }
            cout<<endl;
            */
        }
       // cout<<endl;
    }
}
int main(){
    //srand((unsigned)time(0));
    //freopen("out.txt","w",stdout);
    //freopen("in.txt","r",stdin);
    int t = read();
    while(t--){
        solve();
    }
    return 0;
}