Description

【题意】
给出n个数，m个操作，操作有以下两种：
1、询问区间k小值；
2、交换相邻两个数的权值。

【输入文件】
第一行两个数n，m，表示序列大小和询问组数；
第一行输入n个数，表示原始序列。
接下来Q行，
当opt = 1时输入三个数l，r，k，询问l~r区间第k小的数
当opt = 2时输入一个数p，交换p和p + 1位置上的权值。
对于任何修改或询问都需异或一个lastans，lastans表示上一个答案，初始值为0。

【输出文件】
对于每组询问输出第K小的数。

【输入样例】
7 3
1 5 2 6 3 7 4
1 2 5 3
2 4
1 7 0 6

【输出样例】
5
3

【数据范围】
如果被卡常，请使用#pragma GCC optimize("Ofast")
100%的数据：N<=500000,Q<=500000。

Hint

scy未解决，先贴师兄的代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,a[N],len,lsh[N];
int get(int x){
    return lower_bound(lsh+1,lsh+len+1,x)-lsh;
}
struct trnode{
    int lc,rc,c;
}tr[32*N];
int root[N],trlen;
int build(int nl,int nr){
    trlen++;int now=trlen;
    tr[now]=trnode{-1,-1,0};
    if(nl==nr)tr[now].c=0;
    else{
        int mid=(nl+nr)>>1;
        tr[now].lc=build(nl,mid);
        tr[now].rc=build(mid+1,nr);
    }
    return now;
}
int insert(int pre,int nl,int nr,int x,int c){
    trlen++;int now=trlen;
    tr[now]=tr[pre],tr[now].c+=c;
    if(nl==nr)return now;
    else{
        int mid=(nl+nr)>>1;
        if(x<=mid)tr[now].lc=insert(tr[pre].lc,nl,mid,x,c);
        else tr[now].rc=insert(tr[pre].rc,mid+1,nr,x,c);
        return now;
    }
}
void change(int x){
    root[x]=insert(root[x-1],1,len,a[x+1],1);
    swap(a[x],a[x+1]);
}
int query(int pre,int now,int nl,int nr,int x){
    if(nl==nr)return nl;
    int mid=(nl+nr)>>1;
    int cnt=tr[tr[now].lc].c-tr[tr[pre].lc].c;
    if(x<=cnt)return query(tr[pre].lc,tr[now].lc,nl,mid,x);
    else return query(tr[pre].rc,tr[now].rc,mid+1,nr,x-cnt);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        lsh[i]=a[i];
    }
    sort(lsh+1,lsh+n+1);
    len=unique(lsh+1,lsh+n+1)-lsh-1;
    for(int i=1;i<=n;i++){
        a[i]=get(a[i]);
    }
    root[0]=build(1,len);
    for(int i=1;i<=n;i++){
        root[i]=insert(root[i-1],1,len,a[i],1);
    }
    int last=0;
    for(int i=1;i<=m;i++){
        int op,l,r,k;scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&l,&r,&k);
            l=l^last,r=r^last,k=k^last;
            int ans=query(root[l-1],root[r],1,len,k);
            printf("%d\n",last=lsh[ans]);
        }
        if(op==2){
            scanf("%d",&l);
            l=l^last;
            change(l);
        }
    }
    return 0;
}