Splay WA+TLE 48pts 求调

RT.

Code:

#include<bits/stdc++.h>
using namespace std;
struct P{
    int ch[2];
    int v,z,fa,sz;
}t[2000005];
int rt;
int which_son(int x)
{
    if(t[t[x].fa].ch[0]==x) return 0;
    return 1;
}
void push_up(int x)
{
    t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+t[x].z;
}
void rotate(int x)
{
    int k=which_son(x);
    int fa=t[x].fa,ffa=t[fa].fa,w=t[x].ch[k^1];
    t[fa].ch[k]=w,t[w].fa=fa;
    t[ffa].ch[which_son(fa)]=x,t[x].fa=ffa;
    t[x].ch[k^1]=fa,t[fa].fa=x;
    push_up(fa);
    push_up(x);
}
void splaying(int x,int tp=0)
{
    while(t[x].fa!=tp)
    {
        int fa=t[x].fa,ffa=t[fa].fa;
        if(tp!=ffa)
        {
            if(which_son(fa)==which_son(x)) rotate(fa);
            else rotate(x);
        }
        rotate(x);
    }
    if(tp==0) rt=x;
}
void find(int x)
{
    int mu=rt;
    while(x!=t[mu].v && t[mu].ch[x>t[mu].v]) mu=t[mu].ch[x>t[mu].v];
    splaying(mu);
}
int z;
void insert(int x)
{
    int mu=rt,p=0;
    while(mu && t[mu].v!=x) p=mu,mu=t[mu].ch[x>t[mu].v];
    if(mu) t[mu].z++;
    else
    {
        mu=++z;
        if(p) t[p].ch[x>t[p].v]=mu;
        t[mu].ch[0]=t[mu].ch[1]=0;
        t[mu].v=x,t[mu].fa=p;
        t[mu].sz=t[mu].z=1;
    }
    splaying(mu);
}
int k_th(int x)
{
    int mu=rt;
    while(x)
    {
        if(t[mu].ch[0] && x<=t[t[mu].ch[0]].sz) mu=t[mu].ch[0];
        else if(x>t[t[mu].ch[0]].sz+t[mu].z) x-=t[t[mu].ch[0]].sz+t[mu].z,mu=t[mu].ch[1];
        else
        {
            splaying(mu);
            return mu;
        }
    }
}
int get_rank(int x)
{
    find(x);
    return t[t[rt].ch[0]].sz;
}
int get_pre(int x)
{
    find(x);
    if(t[rt].v<x) return rt;
    int mu=t[rt].ch[0];
    while(t[mu].ch[1]) mu=t[mu].ch[1];
    splaying(mu);
    return mu;
}
int get_nxt(int x)
{
    find(x);
    if(t[rt].v>x) return rt;
    int mu=t[rt].ch[1];
    while(t[mu].ch[0]) mu=t[mu].ch[0];
    splaying(mu);
    return mu;
}
void del(int x)
{
    int pre=get_pre(x),nxt=get_nxt(x);
    splaying(pre);
    splaying(nxt,pre);
    int mu=t[nxt].ch[0];
    if(t[mu].z>1) t[mu].z--,splaying(mu);
    else t[mu].ch[0]=0;
    push_up(nxt);
    push_up(rt);
}
int main()
{
    insert((1<<30)+1);
    insert(-1);
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--)
    {
        int x;
        scanf("%d",&x);
        insert(x);
    }
    int lstans=0,ans=0;
    while(m--)
    {
        int k,x;
        scanf("%d%d",&k,&x);
        x^=lstans;
        if(k==1) insert(x);
        if(k==2) del(x);
        if(k==3)
        {
            int y=get_rank(x);
            ans^=y,lstans=y;
        }
        if(k==4)
        {
            int y=t[k_th(x+1)].v;
            ans^=y,lstans=y;
        }
        if(k==5)
        {
            int y=t[get_pre(x)].v;
            ans^=y,lstans=y;
        }
        if(k==6)
        {
            int y=t[get_nxt(x)].v;
            ans^=y,lstans=y;
        }
    }
    printf("%d",ans);
    return 0;
}