萌新裂开了啊，我的复杂度假了吗。。。

我写的treap和splay都过不去，裂开了，啊我死了，，，救命，都70分t三个点 下面是treap

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1100005;
int ch[N][2],pri[N],val[N],siz[N],cnt[N],node_tot;
int root;
inline void pushup(int x){
    siz[x]=siz[ch[x][0]]+cnt[x]+siz[ch[x][1]];
}
inline int newnode(int v){
    int x=++node_tot;
    ch[x][0]=ch[x][1]=0;
    pri[x]=rand();
    val[x]=v;
    siz[x]=cnt[x]=1;
    return x;
}
inline void rotate(int &x,int d){ // d=0左旋，d=1右旋
    int t=ch[x][d^1];
    ch[x][d^1]=ch[t][d];
    pushup(x); // 这边的pushup可能有冗余的操作
    ch[t][d]=x;
    pushup(x=t);
}
void insert(int &x,int v){
    if(!x){
        x=newnode(v);
    }else if(val[x]==v){
        ++cnt[x];
        ++siz[x];
    }else{
        insert(ch[x][v>val[x]],v);
        if(pri[ch[x][v>val[x]]]>pri[x])rotate(x,v<val[x]); // 维持大根堆特性
    }
    pushup(x); // 递归地pushup因为没有设置指向祖先的指针
}
void delroot(int &x){
    if(ch[x][0]==ch[x][1]){
        x=0;
    }else{
        int t=pri[ch[x][0]]>pri[ch[x][1]]; // 左边的优先级>右边的优先级就右旋
        rotate(x,t);
        delroot(ch[x][t]); // 如果前面是右旋的话：x已经变成左边的节点了，x的右孩子就是原先的节点
    }
}
void del(int &x,int v){
    if(val[x]==v){
        --siz[x];
        if(!--cnt[x])delroot(x); // 出现次数为0了就删掉这个节点
    }else{
        del(ch[x][v>val[x]],v);
    }
    pushup(x);
}
inline int findrank(int v){
    int ans=0,x=root;
    while(x){
        if(val[x]<=v)ans+=siz[ch[x][0]]+(val[x]==v?0:cnt[x]),x=ch[x][1];
        else x=ch[x][0];
    }
    return ans+1;
}
inline int kth(int k){
    int x=root;
    while(k<=siz[ch[x][0]]||k>siz[ch[x][0]]+cnt[x]){
        if(k<=siz[ch[x][0]])x=ch[x][0];
        else k-=siz[ch[x][0]]+cnt[x],x=ch[x][1];
    }
    return val[x];
}
inline int pred(int v){
    int x=root,ans;
    while(x){
        if(val[x]<v){
            ans=val[x];
            x=ch[x][1];
        }else{
            x=ch[x][0];
        }
    }
    return ans;
}
inline int succ(int v){
    int x=root,ans;
    while(x){
        if(val[x]>v){
            ans=val[x];
            x=ch[x][0];
        }else{
            x=ch[x][1];
        }
    }
    return ans;
}
int main(){
#ifdef LOCAL
    freopen("..\\in","r",stdin),freopen("..\\out","w",stdout);
#endif
    pri[0]=-0x3f3f3f3f;
    int n,m,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&v);
        insert(root,v);
    }
    int last=0,ans=0,cmd;
    while(m--){
        scanf("%d%d",&cmd,&v);
        v^=last;
        switch(cmd){
        case 1: // 插入 xx 数
            insert(root,v);
            break;
        case 2: // 删除 xx 数(若有多个相同的数，只删除一个)
            del(root,v);
            break;
        case 3: // 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1 )
            ans^=(last=findrank(v));
            break;
        case 4: // 查询排名为 xx 的数
            ans^=(last=kth(v));
            break;
        case 5: // 求 xx 的前驱(前驱定义为小于 xx，且最大的数)
            ans^=(last=pred(v));
            break;
        case 6: // 求 xx 的后继(后继定义为大于 xx，且最小的数)
            ans^=(last=succ(v));
            break;
        }
    }
    printf("%d",ans);
    return 0;
}

这边是splay

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1100005;
struct Splaytree{
    static inline int ch[N][2],fa[N],siz[N],cnt[N],val[N],node_tot;
    int root;
    Splaytree():root(0){}
    void pushup(int x){
        siz[x]=siz[ch[x][0]]+cnt[x]+siz[ch[x][1]];
    }
    void rotate(int x){
        int y=fa[x],d=ch[y][0]==x;
        fa[ch[y][d^1]=ch[x][d]]=y;
        if(fa[y])ch[fa[y]][ch[fa[y]][1]==y]=x;
        fa[x]=fa[y];
        ch[x][d]=y;
        fa[y]=x;
        pushup(y);
    }
    void splay(int x,int guard){
        for(int y;(y=fa[x])!=guard;rotate(x)){
            if(fa[y]!=guard){
                rotate((ch[fa[y]][0]==y^ch[y][0]==x)?x:y);
            }
        }
        pushup(x);
        if(!guard)root=x;
    }
    void insert(int v){
        int x=root,y=0;
        while(x){
            y=x;
            if(v!=val[x]){
                x=ch[x][v>val[x]];
            }else{
                ++cnt[x];
                splay(x,0);
                return;
            }
        }
        if(!y)root=++node_tot;
        else ch[y][v>val[y]]=++node_tot;
        fa[node_tot]=y;
        val[node_tot]=v;
        cnt[node_tot]=1;
        splay(node_tot,0);
    }
    int find(int v){
        int x=root;
        while(val[x]!=v)x=ch[x][v>val[x]];
        return x;
    }
    int findmax(int x){
        while(ch[x][1])x=ch[x][1];
        return x;
    }
    void delroot(){
        if(!ch[root][0]){
            root=ch[root][1];
            fa[root]=0;
        }else{
            int m=findmax(ch[root][0]);
            splay(m,root);
            ch[m][1]=ch[root][1];
            fa[ch[root][1]]=m;
            fa[m]=0;
            root=m;
            pushup(root);
        }
    }
    void del(int v){
        splay(find(v),0);
        --siz[root];
        if(!--cnt[root])delroot();
    }
    int rank(int v){
        int x=root,ans=0,y=0;
        while(x){
            y=x;
            if(val[x]<=v){
                ans+=siz[ch[x][0]]+(val[x]==v?0:cnt[x]);
                x=ch[x][1];
            }else{
                x=ch[x][0];
            }
        }
        if(y)splay(y,0);
        return ans+1;
    }
    int kth(int k){
        int x=root;
        while(k<=siz[ch[x][0]]||k>siz[ch[x][0]]+cnt[x]){
            if(k<=siz[ch[x][0]])x=ch[x][0];
            else k-=siz[ch[x][0]]+cnt[x],x=ch[x][1];
        }
        splay(x,0);
        return val[x];
    }
    int pred(int v){
        int x=root,ans,y=0;
        while(x){
            y=x;
            if(val[x]<v){
                ans=val[x];
                x=ch[x][1];
            }else{
                x=ch[x][0];
            }
        }
        if(y)splay(y,0);
        return ans;
    }
    int succ(int v){
        int x=root,ans,y=0;
        while(x){
            y=x;
            if(val[x]>v){
                ans=val[x];
                x=ch[x][0];
            }else{
                x=ch[x][1];
            }
        }
        if(y)splay(y,0);
        return ans;
    }
}t;
int main(){
#ifdef LOCAL
    freopen("..\\in","r",stdin),freopen("..\\out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,v;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>v;
        t.insert(v);
    }
    int last=0,ans=0;
    while(m--){
        int cmd,v;
        cin>>cmd>>v;
        v^=last;
        switch(cmd){
        case 1: // 插入 xx 数
            t.insert(v);
            break;
        case 2: // 删除 xx 数(若有多个相同的数，只删除一个)
            t.del(v);
            break;
        case 3: // 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1 )
            ans^=(last=t.rank(v));
            break;
        case 4: // 查询排名为 xx 的数
            ans^=(last=t.kth(v));
            break;
        case 5: // 求 xx 的前驱(前驱定义为小于 xx，且最大的数)
            ans^=(last=t.pred(v));
            break;
        case 6: // 求 xx 的后继(后继定义为大于 xx，且最小的数)
            ans^=(last=t.succ(v));
            break;
        }
    }
    cout<<ans;
    return 0;
}

我写的都不能过啊啊啊