c++之路进阶——codevs4543（普通平衡树）

4543 普通平衡树

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

这是一道水题

顺便祝愿ＬＥＺ和ＺＱＱ　省选ＡＫＡＫＡＫ

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

1 10

样例输出 Sample Output

EOF（无输出）

数据范围及提示 Data Size & Hint

n=100000 所有数字均在-2*10^9到2*10^9内

其实n=5000000才对。。。但是为了不卡评测机

题解：

没有任何技术含量，就是treap基本操作。

代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 struct data{
  6     int l,r,v,size,rnd,w;
  7 }tr[100005];
  8 int n,size,root,ans;
  9 void update(int k)//更新结点信息
 10 {
 11     tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;
 12 }
 13 void rturn(int &k)
 14 {
 15     int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;
 16     tr[t].size=tr[k].size;update(k);k=t;
 17 }
 18 void lturn(int &k)
 19 {
 20     int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;
 21     tr[t].size=tr[k].size;update(k);k=t;
 22 }
 23 void insert(int &k,int x)
 24 {
 25     if(k==0)
 26     {
 27     size++;k=size;
 28     tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=rand();
 29     return;
 30     }
 31     tr[k].size++;
 32     if(tr[k].v==x)tr[k].w++;//每个结点顺便记录下与该节点相同值的数的个数
 33     else if(x>tr[k].v)
 34     {
 35     insert(tr[k].r,x);
 36     if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);//维护堆性质
 37     }
 38     else 
 39     {
 40     insert(tr[k].l,x);
 41     if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
 42     } 
 43 }
 44 void del(int &k,int x)
 45 {
 46     if(k==0)return; 
 47     if(tr[k].v==x)
 48     {
 49     if(tr[k].w>1)
 50     {
 51     tr[k].w--;tr[k].size--;return;//若不止相同值的个数有多个，删去一个
 52     }
 53     if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;//有一个儿子为空
 54     else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
 55     rturn(k),del(k,x);
 56     else lturn(k),del(k,x);
 57     }
 58     else if(x>tr[k].v)
 59     tr[k].size--,del(tr[k].r,x);
 60     else tr[k].size--,del(tr[k].l,x);
 61 }
 62 int query_rank(int k,int x)
 63 {
 64     if(k==0)return 0;
 65     if(tr[k].v==x)return tr[tr[k].l].size+1;
 66     if(x>tr[k].v)return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r,x);
 67     else return query_rank(tr[k].l,x);
 68 }
 69 int query_num(int k,int x)
 70 {
 71     if(k==0)return 0;
 72     if(x<=tr[tr[k].l].size)
 73     return query_num(tr[k].l,x);
 74     else if(x>tr[tr[k].l].size+tr[k].w)
 75     return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
 76     else return tr[k].v;
 77 }
 78 void query_pro(int k,int x)
 79 {
 80     if(k==0)return;
 81     if(tr[k].v<x)
 82     {
 83     ans=k;query_pro(tr[k].r,x);
 84     }
 85     else query_pro(tr[k].l,x);
 86 }
 87 void query_sub(int k,int x)
 88 {
 89     if(k==0)return;
 90     if(tr[k].v>x)
 91     {
 92     ans=k;query_sub(tr[k].l,x);
 93     }
 94     else query_sub(tr[k].r,x);
 95 }
 96 int main()
 97 {
 98     scanf("%d",&n);
 99     int opt,x;
100     for(int i=1;i<=n;i++)
101     {
102     scanf("%d%d",&opt,&x);
103     switch(opt)
104     {
105     case 1:insert(root,x);break;
106     case 2:del(root,x);break;
107     case 3:printf("%d
",query_rank(root,x));break;
108     case 4:printf("%d
",query_num(root,x));break;
109     case 5:ans=0;query_pro(root,x);printf("%d
",tr[ans].v);break;
110     case 6:ans=0;query_sub(root,x);printf("%d
",tr[ans].v);break;
111     }
112     }
113     return 0;
114 }