Splay球调

RT，输入输出改一下原版就能过了，但是这题样例没过去(

#include<iostream>
#include<cstdio>
#define MAXN 100001
#define INF 0x3f3f3f3f
#define root tree[0].ch[1]
#define ls(x) tree[x].ch[0]
#define rs(x) tree[x].ch[1]
#define fa(x) tree[x].fa
using namespace std;
struct node{
    int val;//权值
    int fa;//父亲节点
    int ch[2];//0代表左儿子，1代表右儿子
    int rec;//这个权值的节点出现的次数
    int sum;//子节点的数量
}tree[MAXN];
int tot=0,pointnum=0;
int n,m,ans114514;
bool ident(int x){//判断当前结点是左孩子，还是右孩子。0为左孩子，1为右孩子
    return tree[fa(x)].ch[0]==x?0:1;
}//
void connect(int x,int fa,int how){//x节点将成为fa节点的how孩子
    tree[x].fa=fa;
    tree[fa].ch[how]=x;
}//
void update(int x){
    tree[x].sum=tree[ls(x)].sum+tree[rs(x)].sum+tree[x].rec;
}//
void rotate(int x){//单旋
    int Y=fa(x);
    int R=fa(Y);
    int Yson=ident(x);
    int Rson=ident(Y);
    connect(tree[x].ch[Yson^1],Y,Yson);
    connect(Y,x,Yson^1);
    connect(x,R,Rson);
    update(Y);
    update(x);
}//
void Splay(int x,int to){//双旋
    to=fa(to);
    while(fa(x)!=to){
        int y=fa(x);
        if(tree[y].fa==to) rotate(x);
        else if(ident(x)==ident(y)) rotate(y),rotate(x);
        else rotate(x),rotate(x);
    }
}//
int newpoint(int v,int f){//插入
    tree[++tot].fa=f;
    tree[tot].val=v;
    tree[tot].sum=tree[tot].rec=1;
    return tot;
}
void Insert(int x){//插入
    int now=root;
    if(root==0){
        newpoint(x,0);
        root=tot;
    }else{
        while(1){
            tree[now].sum++;
            if(tree[now].val==x){
                tree[now].rec++;
                Splay(now,root);
                return ;
            }
            int nxt=x<tree[now].val?0:1;
            if(!tree[now].ch[nxt]){
                int p=newpoint(x,now);
                tree[now].ch[nxt]=p;
                Splay(p,root);
                return ;
            }
            now=tree[now].ch[nxt];
        }
    }
}//
int find(int v){//查询位置
    int now=root;
    while(1){
        if(!now) return 0;
        if(tree[now].val==v){
            Splay(now,root);
            return now;
        }
        int nxt=v<tree[now].val?0:1;
        now=tree[now].ch[nxt];
    }
}//
void dele(int x){//删除
    int pos=find(x);
    if(!pos) return ;
    if(tree[pos].rec>1){
        tree[pos].rec--;
        tree[pos].sum--;
        return ;
    }
    else{
        if(!tree[pos].ch[0]&&!tree[pos].ch[1]){
            root=0;
            return ;
        }
        else if(!tree[pos].ch[0]){
            root=tree[pos].ch[1];
            tree[root].fa=0;
            return ;
        }
        else{
            int left=tree[pos].ch[0];
            while(tree[left].ch[1]) left=tree[left].ch[1];
            Splay(left,tree[pos].ch[0]);
            connect(tree[pos].ch[1],left,1);
            connect(left,0,1);
            update(left);
        }
    }
}//
int rak(int v){// 查询值为v的数的排名
    int pos=find(v);
    return tree[ls(pos)].sum+1;
}
int arank(int x){//查询排名为x的数是什么 
    int now=root;
    while(1){
        int used=tree[now].sum-tree[tree[now].ch[1]].sum;
        if(x>tree[tree[now].ch[0]].sum&&x<=used) break;
        if(x<used) now=tree[now].ch[0];
        else x=x-used,now=tree[now].ch[1];
    }
    Splay(now,root);
    return tree[now].val;
}
int lower(int v){//查询v的前驱
    int now=root;
    int ans=-INF;
    while(now){
        if(tree[now].val<v&&tree[now].val>ans) ans=tree[now].val;
        if(v>tree[now].val) now=tree[now].ch[1];
        else now=tree[now].ch[0];
    }
    return ans;
}
int upper(int v){//查询v的后继
    int now=root;
    int ans=INF;
    while(now){
        if(tree[now].val>v&&tree[now].val<ans) ans=tree[now].val;
        if(v<tree[now].val) now=tree[now].ch[0];
        else now=tree[now].ch[1];
    }
    return ans;
}
int opt,x,last;
int main(){
    cin>>n>>m;
    for(int i=1,u;i<=n;i++){
        cin>>u;
        Insert(u);
    }
    for(int i=1;i<=m;i++){
        cin>>opt>>x;
        x^=last;
        if(opt==1){
            Insert(x);
        }
        if(opt==2){
            dele(x);
        }
        if(opt<=2) continue;
        if(opt==3){
            last=rak(x);
        }
        if(opt==4){
            last=arank(x);
        }
        if(opt==5){
            last=lower(x);
        }
        if(opt==6){
            last=upper(x);
        }
        ans114514^=last;
        //cout<<ans114514<<"\n";
    }
    cout<<ans114514;
    return 0;
}