splay的模板（bzoj3224）

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 10532 Solved: 4501
[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

平衡树

平衡树模板题，刚学了，敲一遍熟悉一下。

  1 #include <iostream>
  2 #include <cstdio>
  3 const int N = 1000000 + 11;
  4 using namespace std;
  5 int n,root,sc;
  6 struct balence
  7 {
  8     int son[2],size,cnt,key,f;
  9     void news(int now)
 10     {
 11         son[0] = son[1] = 0; 
 12         size = cnt = 1; key = now; f = 0;
 13     }
 14     void clear()
 15     {
 16         son[0] = son[1] = 0; 
 17         size = cnt = 0; key = f = 0;
 18     }
 19 }tree[N];
 20 
 21 void updata(int now)
 22 {
 23     if(now)
 24     {
 25         tree[now].size = tree[now].cnt;
 26         if(tree[now].son[0]) tree[now].size += tree[tree[now].son[0]].size;
 27         if(tree[now].son[1]) tree[now].size += tree[tree[now].son[1]].size;
 28     }
 29 }
 30 
 31 int get(int x)
 32 {
 33     return x == tree[tree[x].f].son[1];
 34 }
 35 
 36 void rotate(int now)
 37 {
 38     int fa = tree[now].f,gfa = tree[fa].f,whitchx=get(now);
 39     tree[fa].son[whitchx] = tree[now].son[whitchx^1]; tree[tree[fa].son[whitchx]].f = fa;
 40     tree[now].son[whitchx^1] = fa, tree[fa].f = now;
 41     tree[now].f = gfa;
 42     whitchx = (fa == tree[gfa].son[1]);
 43     if(gfa)
 44         tree[gfa].son[whitchx] = now;
 45     updata(fa); updata(now);    
 46 }
 47 
 48 
 49 void splay( int now )
 50 {
 51     for(int i; (i = tree[now].f); rotate(now))
 52     {
 53         if(tree[i].f)
 54             if(get(now) == get(i))rotate(i);
 55     }
 56     root = now;
 57 }
 58 
 59 void insert(int x)
 60 {
 61     if(root == 0) 
 62     {
 63         tree[++sc].news(x); root = sc;
 64         return; 
 65     }
 66     int now = root,fa = 0;
 67     while(1)
 68     {
 69         if(x == tree[now].key)
 70         {
 71             ++tree[now].cnt; updata(now); updata(fa);
 72             splay(now); return;
 73         }
 74         int ze = x > tree[now].key;
 75         fa = now; now = tree[fa].son[ze];
 76         if(!now)
 77         {
 78             tree[++sc].news(x); tree[sc].f = fa; 
 79             tree[fa].son[ze] = sc; 
 80             updata(fa); splay(sc);
 81             return;
 82         }
 83     }
 84 }
 85 
 86 int find(int x)
 87 {
 88     int now = root,ans = 0;
 89     while(1)
 90     {
 91         if(x < tree[now].key) now = tree[now].son[0];
 92         else
 93         {
 94             ans += (tree[now].son[0])?tree[tree[now].son[0]].size:0;
 95             if( x == tree[now].key ) 
 96             {
 97                 splay(now);
 98                 return ans + 1;
 99             }
100             ans += tree[now].cnt;
101             now = tree[now].son[1];
102         }
103     }
104 }
105 
106 int findx(int x)
107 {
108     int now = root,sy = x;
109     while(1)
110     {
111         
112         if(sy <= tree[tree[now].son[0]].size&&tree[now].son[0]) now = tree[now].son[0];
113         else
114         {
115             int rank = (tree[now].son[0])?tree[tree[now].son[0]].size:0;
116             rank += tree[now].cnt;
117             if(rank >= sy) return tree[now].key;
118             sy -= rank; now = tree[now].son[1];
119         }
120     }
121 }
122 
123 int pre(int now)
124 {
125     now = tree[now].son[0];
126     while(tree[now].son[1])now = tree[now].son[1];
127     return now;
128 }
129 
130 int nxt(int now)
131 {
132     now = tree[now].son[1];
133     while(tree[now].son[0])now = tree[now].son[0];
134     return now;
135 }
136 
137 
138 
139 void del(int x)
140 {
141     int ss = find(x);
142     if(tree[root].cnt > 1) { --tree[root].cnt; --tree[root].size; return;}
143     if(!tree[root].son[0] && !tree[root].son[1]) { tree[root].clear();root = 0; return; }
144     if(!tree[root].son[0] || !tree[root].son[1])
145     {
146         int whitch = !tree[root].son[1];
147         int root_y = root; root = tree[root_y].son[whitch^1]; 
148         tree[root].f = 0; tree[root_y].clear();return;
149     }
150     int pres = pre(root),root_y = root;
151     splay(pres);
152     tree[root].son[1] = tree[root_y].son[1];
153     tree[tree[root_y].son[1]].f = root;
154     tree[root_y].clear(); updata(root);
155 
156 }
157 
158 int main()
159 {
160 
161     scanf("%d
",&n);
162     int opt,x; root = 0,sc = 0;
163     while(n--)
164     {
165         scanf("%d%d",&opt,&x);
166         switch(opt)
167         {
168             case 1: insert(x); break;
169             case 2: del(x); break;
170             case 3: printf("%d
",find(x)); break;
171             case 4: printf("%d
",findx(x)); break;
172             case 5: insert(x); printf("%d
",tree[pre(root)].key); del(x); break;
173             case 6: insert(x); printf("%d
",tree[nxt(root)].key); del(x); break;
174         }
175     
176     }
177     return 0;
178 }