TLE#10求优化

#include<bits/stdc++.h>
//#define int long long
#define mi(...) <%__VA_ARGS__%>
using namespace std;
namespace Faster {
inline bool _u(char ch) { return ch >= '0' && ch <= '9'; }
//char buf[1 << 23], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 23, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {int x = 0, f = 1;char ch = getchar();for (; !_u(ch); ch = getchar())if (ch == '-')f = -f;for (; _u(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);return x * f;}
inline void write(int num) {static int sta[39], top = 0;if (num < 0)putchar('-'), num *= -1;do sta[++top] = num % 10, num /= 10;while (num);while (top) putchar(sta[top--] | 48);return;}
}using namespace Faster;
const int N=1e6+2e5+10;
vector<int>newnode;
int fa[N],son[N][2],val[N],tot,cnt[N],sz[N];
int rt;

inline void clear(int u){son[u][0]=son[u][1]=fa[u]=val[u]=cnt[u]=sz[u]=0;}

inline bool _son(int u) {return u==son[fa[u]][1];}

inline void update(int u){
    u&&(sz[u]=cnt[u]+(son[u][0]?sz[son[u][0]]:0)+(son[u][1]?sz[son[u][1]]:0));
    return;
}

inline void rotate(int u){
    int f=fa[u],g=fa[fa[u]];
    bool flag=_son(u),flagf=_son(f);
    son[f][flag]=son[u][flag^1];
    if(son[u][flag^1]) fa[son[u][flag^1]]=f;
    son[u][flag^1]=f;
    fa[f]=u;
    fa[u]=g;
    if(g) son[g][flagf]=u;
    else rt=u;
    return update(f),update(u);
}

inline void splay(int u,int to=0){
    if(!u)return;
    for(;fa[u]!=to;)
        fa[fa[u]]!=to?rotate(_son(u)==_son(fa[u])?fa[u]:u):rotate(u);
    if(!to)
    rt=u;
}

inline void insert(int x){
    if(!rt){
        if(newnode.empty())
            rt=++tot;
        else
            rt=newnode.back(),newnode.pop_back();
        clear(rt);
        son[rt][0]=son[rt][1]=fa[rt]=0;
        sz[rt]=++cnt[rt];
        val[rt]=x;
        return;
    }
    int now=rt;
    while(1){
        if(val[now]==x){
            ++cnt[now];
            update(now);
            splay(now);
            return;
        }
        if(!son[now][x>val[now]]){
            int t; 
            if(newnode.empty())
                t=++tot;
            else
                t=newnode.back(),newnode.pop_back();
            clear(t);
            son[now][x>val[now]]=t;
            sz[t]=++cnt[t];
            fa[t]=now;
            val[t]=x;
            update(t);
            splay(t);
            return;
        }
        now=son[now][x>val[now]];
    }
}

inline int fnd_rnk(int u,int x){
    if(!u)return 1;
    int res=0;
    while(1){
        if(x<val[u]) u=son[u][0];
        else{
            res+=sz[son[u][0]];
            if(!u) return res+1;
            if(x==val[u]){
                splay(u);
                return res+1;
            }
            res+=cnt[u];
            u=son[u][1];
        }
    }
}

inline int fnd_kth(int u,int x){
    if(!u)return 0;
    while(1){
        if(son[u][0]&&sz[son[u][0]]>=x) u=son[u][0];
        else {
            x-=sz[son[u][0]]+cnt[u];
            if(x<=0||!son[u][1]){
                splay(u);
                return u;
            }
            u=son[u][1];
        }
    }
}
inline int fnd_pre(int x=0){
    int now=son[rt][0];
    if(now)
        while(son[now][1]) now=son[now][1];
    splay(now);
    return now;
}

inline int fnd_after(int x=0){
    int now=son[rt][1];
    if(now)
        while(son[now][0]) now=son[now][0];
    splay(now);
    return now;
}

inline void del(int u){
    fnd_rnk(rt,u);
    if(cnt[rt]>1){
        --cnt[rt];
        update(rt);
        return;
    }
    if(!son[rt][0]||!son[rt][1]){
        u=rt;
        rt=son[rt][0]|son[rt][1];
        fa[rt]=0;
        clear(u);
        newnode.push_back(u);
        return;
    }
    u=rt;
    int x=fnd_pre();
    fa[son[u][1]]=x;
    son[x][1]=son[u][1];
    clear(u);
    newnode.push_back(u);
    update(x);
    return;

}
int n,m;
int ans=0,lst=0;
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;++i) insert(read());
    for(int i=1,op,x;i<=m;++i){
        op=read(),x=read()^lst;
        switch(op){
            case 1:insert(x);break;
            case 2:del(x);break;
            case 3:ans^=(lst=fnd_rnk(rt,x));break;
            case 4:ans^=(lst=val[fnd_kth(rt,x)]);break;
            case 5:insert(x);ans^=(lst=val[fnd_pre(x)]);del(x);break;
            case 6:insert(x);ans^=(lst=val[fnd_after(x)]);del(x);break;
        }
    }
    write(ans),puts("");
    return(0-0);
 }