3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 22215 Solved: 9975
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

1.n的数据范围：n<=100000

2.每个数的数据范围：[-2e9,2e9]

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 
  6 struct Treap
  7 {
  8     int left,right,val,size,rnd,w;
  9 }tree[100005];
 10 int n,size,root,ans;
 11 
 12 void update(int k)
 13 {
 14     tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+tree[k].w;
 15 }
 16 
 17 void lturn(int &k)
 18 {
 19     int t=tree[k].right;
 20     tree[k].right=tree[t].left;
 21     tree[t].left=k;
 22     tree[t].size=tree[k].size;
 23     update(k);
 24     k=t;
 25 }
 26 
 27 void rturn(int &k)
 28 {
 29     int t=tree[k].left;
 30     tree[k].left=tree[t].right;
 31     tree[t].right=k;
 32     tree[t].size=tree[k].size;
 33     update(k);
 34     k=t;
 35 }
 36 
 37 void insert(int &k,int x)
 38 {
 39     if(k==0)
 40     {
 41         size++;k=size;
 42         tree[k].size=tree[k].w=1;
 43         tree[k].val=x;
 44         tree[k].rnd=rand();
 45         return;
 46     }
 47     tree[k].size++;
 48     if(tree[k].val==x) tree[k].w++;
 49     else if(x>tree[k].val)
 50     {
 51         insert(tree[k].right,x);
 52         if(tree[tree[k].right].rnd<tree[k].rnd) lturn(k);
 53     }
 54     else
 55     {
 56         insert(tree[k].left,x);
 57         if(tree[tree[k].left].rnd<tree[k].rnd) rturn(k);
 58     }
 59 }
 60 
 61 void del(int &k,int x)
 62 {
 63     if(k==0) return;
 64     if(tree[k].val==x)
 65     {
 66         if(tree[k].w>1)
 67         {
 68             tree[k].w--;tree[k].size--;
 69             return;
 70         }
 71         if(tree[k].left*tree[k].right==0) k=tree[k].left+tree[k].right;
 72         else if(tree[tree[k].left].rnd<tree[tree[k].right].rnd) rturn(k),del(k,x);
 73             else lturn(k),del(k,x);
 74     }
 75     else
 76     {
 77         tree[k].size--;
 78         if(x>tree[k].val) del(tree[k].right,x);
 79         else del(tree[k].left,x);
 80     }
 81 }
 82 
 83 int query_rank(int k,int x)
 84 {
 85     if(k==0) return 0;
 86     if(tree[k].val==x) return tree[tree[k].left].size+1;
 87     else if(x>tree[k].val)
 88         return tree[tree[k].left].size+tree[k].w+query_rank(tree[k].right,x);
 89     else return query_rank(tree[k].left,x);
 90 }
 91 
 92 int query_num(int k,int x)
 93 {
 94     if(k==0) return 0;
 95     if(x<=tree[tree[k].left].size)
 96         return query_num(tree[k].left,x);
 97     else if(x>tree[tree[k].left].size+tree[k].w)
 98         return query_num(tree[k].right,x-tree[tree[k].left].size-tree[k].w);
 99     else return tree[k].val;
100 }
101 
102 void query_pro(int k,int x)
103 {
104     if(k==0) return;
105     if(tree[k].val<x)
106     {
107         ans=k;
108         query_pro(tree[k].right,x);
109     }
110     else query_pro(tree[k].left,x);
111 }
112 
113 void query_sub(int k,int x)
114 {
115     if(k==0) return;
116     if(tree[k].val>x)
117     {
118         ans=k;
119         query_sub(tree[k].left,x);
120     }
121     else query_sub(tree[k].right,x);
122 }
123 
124 int main()
125 {
126     scanf("%d",&n);
127     int opt,x;
128     for(int i=1;i<=n;i++)
129     {
130         scanf("%d %d",&opt,&x);
131         switch(opt)
132         {
133             case 1:insert(root,x);break;
134             case 2:del(root,x);break;
135             case 3:printf("%d
",query_rank(root,x));break;
136             case 4:printf("%d
",query_num(root,x));break;
137             case 5:ans=0;query_pro(root,x);printf("%d
",tree[ans].val);break;
138             case 6:ans=0;query_sub(root,x);printf("%d
",tree[ans].val);break;
139         }
140     }
141     return 0;
142 }