bzoj3224普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

对于操作3,4,5,6每行输出一个数，表示对应答案

平衡树

明确告知你就是平衡树。

写一个treap就好

<pre name="code" class="cpp">#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
struct treap
{
    int l,r,v,size,rnd,w;
}t[100010];
int n,size,root,ans;
 
void update(int k);
void insert(int &k, int x);
void left_turn(int &k);
void right_turn(int &k);
int query_rank(int k, int x);
int query_num(int k, int x);
void query_pre(int k, int x);
void query_nst(int k, int x); 
void del(int &k, int x);
 
int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        switch(opt)
        {
            case 1: insert(root,x);break;
            case 2:  del(root,x);break;
            case 3: printf("%d\n",query_rank(root,x));break;
            case 4: printf("%d\n",query_num(root,x));break;
            case 5: ans = 0;query_pre(root,x);printf("%d\n",t[ans].v);break;
            case 6: ans = 0;query_nst(root,x);printf("%d\n",t[ans].v);break;
        }
    }
     
    return 0;
}
 
void update(int k)
{
    t[k].size = t[ t[k].l ].size + t[ t[k].r ].size + t[k].w;
}
 
void insert(int &k, int x)
{
    if(k == 0)
    {
        size ++;
        k = size;
        t[k].size = t[k].w = 1;
        t[k].v = x;
        t[k].rnd = rand();
        return;
    }
    t[k].size ++;
    if(t[k].v == x) t[k].w ++;
    else
        if(x > t[k].v)
        {
            insert(t[k].r,x);
            if(t[ t[k].r ].rnd < t[k].rnd) left_turn(k);
        }
        else
        {
            insert(t[k].l,x);
            if(t[ t[k].l ].rnd < t[k].rnd) right_turn(k);
        }
}
 
void right_turn(int &k)
{
    int p = t[k].l;
    t[k].l = t[p].r;
    t[p].r = k;
    t[p].size = t[k].size;
    update(k);
    k = p;
}
 
void left_turn(int &k)
{
    int p = t[k].r;
    t[k].r = t[p].l;
    t[p].l = k;
    t[p].size = t[k].size;
    update(k);
    k = p;
}
 
int query_rank(int k, int x)
{
    if(k == 0) return 0;
    if(t[k].v == x) return t[ t[k].l ].size + 1;
    else if(x > t[k].v) return t[ t[k].l ].size + t[k].w + query_rank(t[k].r,x);
    else return query_rank(t[k].l,x);
}
 
int query_num(int k, int x)
{
    if(k == 0) return 0;
    if(x <= t[ t[k].l ].size) return query_num(t[k].l,x);
    else if(x > t[ t[k].l ].size + t[k].w) return query_num(t[k].r,x - t[ t[k].l ].size - t[k].w);
    else return t[k].v;
}
 
void query_pre(int k, int x)
{
    if(k == 0)return;
    if(t[k].v < x)
    {
        ans = k;
        query_pre(t[k].r,x);
    }
    else query_pre(t[k].l,x);
}
 
void query_nst(int k, int x)
{
    if(k == 0)return;
    if(t[k].v > x)
    {
        ans = k;
        query_nst(t[k].l,x);
    }
    else query_nst(t[k].r,x);   
}
 
void del(int &k ,int x)
{
    if(k == 0) return;
    if(t[k].v == x)
    {
        if(t[k].w > 1)
        {
            t[k].w --;
            t[k].size --;
            return;
        }
        if(t[k].l * t[k].r == 0) k = t[k].l + t[k].r;
        else
            if(t[ t[k].l ].rnd < t[ t[k].r ].rnd) right_turn(k),del(k,x);
        else left_turn(k),del(k,x);
    }
    else if(t[k].v < x) t[k].size --,del(t[k].r,x);
    else t[k].size --, del(t[k].l,x);
     
}