玄学问题求助

有图为据 本地AC提交TLE

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
struct splay_tree{
    int fa,val,ch[2],size,cnt;
}t[3400100];
int tot=0,rt,last,ans,Maxn=2147483645;
void maintain(int x){t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;}
int get(int x){return x==t[t[x].fa].ch[1];}
void rotate(int x)
{
    int y=t[x].fa,z=t[y].fa,k=get(x);
    t[y].ch[k]=t[x].ch[k^1];
    if(t[x].ch[k^1]) t[t[x].ch[k^1]].fa=y;
    t[x].ch[k^1]=y;
    t[y].fa=x;
    t[x].fa=z;
    if(z) t[z].ch[y==t[z].ch[1]]=x;
    maintain(y);maintain(x);
    return ;
}
void splay(int x,int goal)
{
    while(t[x].fa!=goal)
    {
        int y=t[x].fa,z=t[y].fa;
        if(z!=goal)
        {
            if(get(x)==get(y)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if(goal==0) rt=x;
}
void find(int x)
{
    if(rt==0) return ;
    int u=rt;
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
    {
        u=t[u].ch[x>t[u].val];
    }
    splay(u,0);
}
void insert(int x)
{
    int u=rt,f=0;
    while(u&&x!=t[u].val)
    {
        f=u;
        u=t[u].ch[x>t[u].val];
    }
    if(u) t[u].cnt++;
    else
    {
        u=++tot;
        t[u].ch[0]=t[u].ch[1]=0;
        t[u].val=x;
        t[u].size=t[u].cnt=1;
        t[u].fa=f;
        if(f) t[f].ch[x>t[f].val]=u;
    }
    splay(u,0);
}
int kth(int k)
{
    int u=rt;
    while(1)
    {
        if(t[u].ch[0]&&k<=t[t[u].ch[0]].size)
        {
            u=t[u].ch[0];
        }
        else if(k>t[t[u].ch[0]].size+t[u].cnt)
        {
            k-=t[t[u].ch[0]].size+t[u].cnt;
            u=t[u].ch[1];
        }
        else
        {
            splay(u,0);
            return u;
        }
    }
}
int pre(int x)
{
    find(x);
    if(t[rt].val<x) return rt;
    int u=t[rt].ch[0];
    while(t[u].ch[1]) u=t[u].ch[1];
    splay(u,0);
    return u;
}
int nxt(int x)
{
    find(x);
    if(t[rt].val>x) return rt;
    int u=t[rt].ch[1];
    while(t[u].ch[0]) u=t[u].ch[0];
    splay(u,0);
    return u;
}
int del(int x)
{
    int last=pre(x),next=nxt(x);
    splay(last,0);splay(next,last);
    int u=t[next].ch[0];
    if(t[u].cnt>1) t[u].cnt--,splay(u,0);
    else t[next].ch[0]=0;
    maintain(next),maintain(rt);
}
int read()
{
    int x=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*w;
}
int main()
{
    int n,m;
    n=read();m=read();
    insert(Maxn);
    insert(-Maxn);
    for(int i=1;i<=n;i++)
    {
        int x;
        x=read();
        insert(x);
    }
    for(int i=1;i<=m;i++)
    {
        int op,x;
        op=read();x=read();
        x^=last;
        if(op==1) insert(x);
        if(op==2) del(x);
        if(op==3)
        {
            find(x);
            if(t[rt].val>=x) last=t[t[rt].ch[0]].size;
            else last=t[t[rt].ch[0]].size+t[rt].cnt;
            ans^=last;
        }
        if(op==4)
        {
            last=t[kth(x+1)].val;
            ans^=last;
        }
        if(op==5)
        {
            last=t[pre(x)].val;
            ans^=last;
        }
        if(op==6)
        {
            last=t[nxt(x)].val;
            ans^=last;
        }
    }
    cout<<ans;
    return 0;
}