BZOJ_3224_普通平衡树_(Treap)

描述

http://www.lydsy.com/JudgeOnline/problem.php?id=3224

Treap模板题.支持如下几种操作:

1.插入;

2.删除;

3.rank(x);

4.kth(k);

5.pre(x);

6.suc(x);

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 7395 Solved: 3124
[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.每个数的数据范围：[-1e7,1e7]

数据如下http://pan.baidu.com/s/1jHMJwO2

Source

平衡树

分析

写多了就熟了...昨天看了书,今天调试的时候敲了好多遍,感觉满脑子是tree+heap.

p.s.

1.rank,kth,pre,suc函数都可以写成非递归的形式.

2.remove函数有两种写法:

(1).LRJ白书上的方法:

　　如果待删除节点只有一个子树,则用该子树代替待删除节点,删除待删除节点即可.如果有两个子树,则将优先值小的(小根堆)子树旋转上去,再在另一　　个子树中递归删除待删除节点,每次这样的旋转操作都会减小子树,最终会达到第一种情况.

(2).在题解里看来的方法:

　　如果待删除节点没有子树,那么可以直接删除.如果有子树,则不管有两个还是一个,将优先值小的子树旋转上去(这里注意可以将null的优先值设为　　　INF),然后再在另一个子树中递归删除节点,每次这样的旋转操作都会减小子树,最终会达到第一种情况.

  1 #include <cstdio>
  2 #include <cstdlib>
  3 using namespace std;
  4 
  5 const int oo=~0u<<1;
  6 
  7 struct Treap{
  8     struct node{
  9         node* ch[2];
 10         int v,s,r,c;
 11         node(int v,node *t):v(v){ ch[0]=ch[1]=t; r=rand(); s=c=1; }
 12         bool operator < (const node &rhs) const { return r<rhs.r; }
 13         void push_up(){ s=ch[0]->s+ch[1]->s+c; }
 14     }*root,*null;
 15     Treap(){
 16         null=new node(0,0);
 17         null->s=null->c=0;
 18         null->r=oo;
 19         root=null;
 20     }
 21     void rotate(node* &o,bool d){
 22         node* k=o->ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o;
 23         o->push_up(); k->push_up(); o=k;
 24     }
 25     void insert(node* &o,int x){
 26         if(o==null) o=new node(x,null);
 27         else{
 28             if(o->v==x){
 29                 o->c++; o->s++;
 30             }
 31             else{
 32                 bool d=x>o->v;
 33                 insert(o->ch[d],x);
 34                 if(o->ch[d]<o) rotate(o,!d);
 35                 o->push_up();
 36             }
 37         }
 38     }
 39     void remove(node* &o,int x){
 40         if(o->v==x){
 41             if(o->c>1) o->c--;
 42             else{
 43                 if(o->ch[0]!=null&&o->ch[1]!=null){
 44                     bool d=o->ch[0]<o->ch[1];
 45                     rotate(o,d); remove(o->ch[d],x);
 46                 }
 47                 else{
 48                     node* u=o;
 49                     if(o->ch[0]==null) o=o->ch[1];
 50                     else o=o->ch[0];
 51                     delete u;
 52                 }
 53             }
 54         }
 55         else{
 56             bool d=x>o->v;
 57             remove(o->ch[d],x);
 58         }
 59         if(o!=null) o->push_up();
 60     }
 61     int kth(node* o,int k){
 62         int s=o->ch[0]->s+o->c;
 63         if(k>o->ch[0]->s&&k<=s) return o->v;
 64         if(k<=o->ch[0]->s) return kth(o->ch[0],k);
 65         else return kth(o->ch[1],k-s);
 66     }
 67     int rank(node *o,int x){
 68         int s=o->ch[0]->s+o->c;
 69         if(x==o->v) return o->ch[0]->s+1;
 70         if(x<o->v) return rank(o->ch[0],x);
 71         else return s+rank(o->ch[1],x);
 72     }
 73     int pre(int x){
 74         node* t=root;
 75         int ret=0;
 76         while(t!=null){
 77             if(t->v<x){
 78                 ret=t->v;
 79                 t=t->ch[1];
 80             }
 81             else t=t->ch[0];
 82         }
 83         return ret;
 84     }
 85     int suc(int x){
 86         node *t=root;
 87         int ret=0;
 88         while(t!=null){
 89             if(t->v>x){
 90                 ret=t->v;
 91                 t=t->ch[0];
 92             }
 93             else t=t->ch[1];
 94         }
 95         return ret;
 96     }
 97 }tree;
 98 
 99 int main()
100 {
101     int n,a,b;
102     scanf("%d",&n);
103     while(n--){
104         scanf("%d%d",&a,&b);
105         switch(a){
106             case(1):tree.insert(tree.root,b);break;
107             case(2):tree.remove(tree.root,b);break;
108             case(3):printf("%d
",tree.rank(tree.root,b));break;
109             case(4):printf("%d
",tree.kth(tree.root,b));break;
110             case(5):printf("%d
",tree.pre(b));break;
111             case(6):printf("%d
",tree.suc(b));break;
112         }
113     }
114     return 0;
115 }

View Code