萌新写的Treap树挂掉了，86pts，前两个点WA，后面都AC了。

请求大佬看看细节有没有写错。

大佬们可以主要看看Insert函数和build函数和zig zag还有getrank函数。这里萌新下载了第一组测试用例供大佬们参考

sample1:

intput:

4
1 10
1 30
1 20
3 21

Ture output:

3

My output:

2

小句蒻第一次学，代码根lyd大佬的差不多，实在是见笑了。

码风良好，注释很全。

Code：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>

#define MAXN 10000005

using namespace std;

struct treap{
    int l,r;
    int val, typ; //关键码，随机生成的权值
    int cnt,siz; //重复的次数，子树的大小
};
treap num[MAXN];

int n;

int tot; //标记的节点编号
int root,INF=0x7fffffff;

int New(int val){ //新建节点
    num[++tot].val=val;
    num[tot].typ=rand();
    num[tot].cnt=1;
    num[tot].siz=1;
    return tot;
}

void update(int u){ //更新子树的大小
    num[u].siz=num[num[u].l].siz+num[num[u].r].siz+num[u].cnt;
}

void build(){
    New(-INF); New(INF);
    root=1;
    num[1].r=2;
    update(root);
    return ;
}

int getval(int u,int rank){ //根据排名得知数值
    if(u==0) return INF;
    if(num[num[u].l].siz >= rank) {
        return getval(num[u].l,rank);
    }
    if(num[num[u].l].siz+num[u].cnt>=rank) {
        return num[u].val;
    }
    return getval(num[u].r,rank-num[num[u].l].siz-num[u].cnt);
}

int getrank(int u,int val){
    if(u==0) return 0;
    if(val==num[u].val){
        return num[num[u].l].siz+1;
    }
    if(val<num[u].val){
        return getrank(num[u].l, val);
    }
    return getrank(num[u].r,val)+num[num[u].l].siz+num[u].cnt;
}

void zagg(int &u){ //左旋
    int v=num[u].r;
    num[u].r=num[v].l;
    num[v].l=u;
    u=v;
    update(num[u].l);update(u);
}

void zigg(int &u){ //右旋
    int v=num[u].l;
    num[u].l=num[v].r;
    num[v].r=u;
    u=v;
    update(num[u].r); update(u);
    return ;
}

void Insert(int &u, int val){
    if(u==0){
        u=New(val);
        return ;
    }
    if(val==num[u].val) {
        num[u].cnt+=1;
        update(u);
        return ;
    }
    if(val < num[u].val){
        Insert(num[u].l,val);
        if(num[u].typ < num[num[u].l].typ){
            zigg(u);
        }
    }
    else{
        Insert(num[u].r,val);
        if(num[u].typ < num[num[u].r].typ){
            zagg(u);
        }
    }
    update(u);
}

int getpre(int val){
    int ans=1;
    int u=root;
    while(u){
        if(val==num[u].val){
            if(num[u].l>0){
                u=num[u].l;
                while(num[u].r>0){
                    u=num[u].r;
                }
                ans=u;
            }
            break;
        }
        if(num[u].val<val && num[u].val>num[ans].val){
            ans=u;
        }
        if(val<num[u].val){
            u=num[u].l;
        }
        else u=num[u].r;
    }

    return num[ans].val;
}

int getsuc(int val){
    int ans=2;
    int u=root;
    while(u){
        if(val==num[u].val){
            if(num[u].r>0){
                u=num[u].r;
                while(num[u].l>0){
                    u=num[u].l;
                }
                ans=u;
            }
            break;
        }
        if(num[u].val>val && num[u].val<num[ans].val){
            ans=u;
        }
        if(val<num[u].val){
            u=num[u].l;
        }
        else {
            u=num[u].r;
        }
    }

    return num[ans].val;
}

void del(int &u,int val){
    if(u==0){
        return ;
    }
    if (val==num[u].val){
        if(num[u].cnt>1){
            num[u].cnt-=1;
            update(u);
            return ;
        }
        if(num[u].l || num[u].r) {
            if(num[u].r==0||num[num[u].l].typ>num[num[u].r].typ){
                zigg(u);
                del(num[u].r,val);
            }
            else {
                zagg(u);
                del(num[u].l,val);
            }
            update(u);
        }
        else u=0;
        return ;
    }

    if(val<num[u].val){
        del(num[u].l,val);
    }
    else {
        del(num[u].r,val);
    }
    update(u);
}

int main(){
    build();
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1){
            Insert(root,x);
        }
        if(opt==2){
            del(root,x);
        }
        if(opt==3){
            printf("%d\n",getrank(root, x)-1);
        }
        if(opt==4){
            printf("%d\n",getval(root, x+1));
        }
        if(opt==5){
            printf("%d\n",getpre(x));
        }
        if(opt==6){
            printf("%d\n",getsuc(x));
        }
    }
    return 0;
}

大佬帮忙看看再走吧！小橘蒻会永远记得恩人的！