萌新Splay 96pts求调，#10 TLE

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdarg.h>
#include<ctype.h>
#define chang 1000000005
int n,m,opt,xi,ans,last;
typedef struct kk
{
    int val,siz,cnt;
    struct kk *son[2],*fa;
}hh;
hh *root;
hh *create(int w,hh *par)
{
    hh *node=(hh*)malloc(sizeof(hh));
    node->val=w;node->siz=node->cnt=1;
    node->son[0]=node->son[1]=NULL;node->fa=par;
    return node;
}
void bf(hh *node,hh *par,int w)
{
    if (node) node->fa=par;
    if (par) par->son[w]=node;
    else root=node;
}
int wson(hh *node,hh *par)
{
    if (!par) return 0;
    return (par->son[1]==node);
}
void pushup(hh *node)
{
    if (!node) return;
    node->siz=node->cnt;
    if (node->son[0]) node->siz+=node->son[0]->siz;
    if (node->son[1]) node->siz+=node->son[1]->siz;
}
void rotate(hh *node)
{
    hh *p=node->fa;hh *q=p->fa;
    int r=wson(node,p),u=wson(p,q);
    bf(node->son[r^1],p,r);
    bf(p,node,r^1);
    bf(node,q,u);
    pushup(p);
}
void splay(hh *node,hh *par)
{
    while (node->fa!=par)
    {
        hh *p=node->fa;hh *q=p->fa;
        if (q!=par) wson(node,p)^wson(p,q)?rotate(p):rotate(node);
        rotate(node);
    }
    pushup(node);
}
void add(int w)
{
    if (!root)
    {
        root=create(w,NULL);
        return;
    }
    for (hh *x=root;x;x=x->son[x->val<=w])
    {
        if (x->val==w)
        {
            x->cnt++;
            splay(x,NULL);
            return;
        }
        if (!x->son[x->val<=w])
        {
            x->son[x->val<=w]=create(w,x);
            splay(x->son[x->val<=w],NULL);
            return;
        }
    }
}
void find(int w)
{
    hh *x=root;
    while (x&&x->son[x->val<w]&&x->val!=w) x=x->son[x->val<w];
    splay(x,NULL);
}
int findkth(int w)
{
    hh *x=root;
    while (x)
    {
        int left=x->son[0]?x->son[0]->siz:0;
        if (left+x->cnt>=w&&left<w){splay(x,NULL);return x->val;}
        if (left>=w) x=x->son[0];
        else w-=left+x->cnt,x=x->son[1];
    }
    return 0;
}
void del(int w)
{
    find(w);
    if (root->val!=w) return;
    hh *x=root;
    if (x->cnt>1){x->cnt--;x->siz--;return;}
    if ((!x->son[0])&&(!x->son[1]))
    {
        root=NULL;
        free(x);
        return;
    }
    if (!x->son[0])
    {
        root=x->son[1];
        if (root) root->fa=NULL;
        free(x);pushup(root);
        return;
    }
    if (!x->son[1])
    {
        root=x->son[0];
        if (root) root->fa=NULL;
        free(x);pushup(root);
        return;
    }
    hh *y=x->son[0];
    while (y->son[1]) y=y->son[1];
    splay(y,x);
    root=y;root->fa=NULL;
    bf(x->son[1],y,1);
    free(x);pushup(root);
}
int pai(int w)
{
    int ans=1;
    add(w);
    if (root->son[0]) ans+=root->son[0]->siz;
    del(w);
    return ans;
}
int pre(int w)
{
    add(w);
    hh *x=root->son[0];
    if (!x) return 0;
    while (x->son[1]) x=x->son[1];
    del(w);
    splay(x,NULL);
    return x->val;
}
int nxt(int w)
{
    add(w);
    hh *x=root->son[1];
    if (!x) return 0;
    while (x->son[0]) x=x->son[0];
    del(w);
    splay(x,NULL);
    return x->val;
}
int main(void)
{
    scanf("%d%d",&n,&m);
    for (int x=1;x<=n;x++)
        scanf("%d",&xi),add(xi);
    for (int x=1;x<=m;x++)
    {
        scanf("%d%d",&opt,&xi);
        xi^=last;
        if (opt==1) add(xi);
        else if (opt==2) del(xi);
        else if (opt==3) last=pai(xi),ans^=last;
        else if (opt==4) last=findkth(xi),ans^=last;
        else if (opt==5) last=pre(xi),ans^=last;
        else if (opt==6) last=nxt(xi),ans^=last;
    }
    printf("%d",ans);
    return 0;
}