既Size Balanced Tree。
左旋 右旋 维护 ： 这个比较容易理解，《Size Balanced Tree》对维护操作的复杂度分析是均摊O(1)，优美
插入：普通BST插入，进行树形状的调整
删除：用BST的删除方法，要找到删除节点的最小关键字或最大关键字，来进行替换。
代码
1 #include
2 #include
3 using namespace std;
4
5 const int maxn = 100005;
6 int NEW = 0, n, m;
7 int size[maxn], left[maxn], right[maxn], key[maxn];
8 int val[maxn];
9
10 void Left_Rotate(int &x) {
11 int k = right[x];
12 right[x] = left[k];
13 left[k] = x;
14 size[k] = size[x];
15 size[x] = size[ left[x] ] + size[ right[x] ] + 1;
16 x = k;
17 }
18
19 void Right_Rotate(int &x) {
20 int k = left[x];
21 left[x] = right[k];
22 right[k] = x;
23 size[k] = size[x];
24 size[x] = size[ left[x] ] + size[ right[x] ] + 1;
25 x = k;
26 }
27
28 void Maintain(int &x, bool Right) {
29 if(!x) return ;
30 if(!Right) {
31 if(size[ left[ left[x] ] ] > size[ right[x] ])
32 Right_Rotate(x);
33 else if(size[ right[ left[x] ] ] > size[ right[x] ])
34 Left_Rotate( left[x] ) , Right_Rotate(x);
35 else
36 return ;
37 } else {
38 if(size[ right[ right[x] ] ] > size[ left[x] ])
39 Left_Rotate(x);
40 else if(size[ left[ right[x] ] ] > size[ left[x] ])
41 Right_Rotate( right[x] ) , Left_Rotate(x);
42 else
43 return ;
44 }
45 Maintain(left[x] , false);
46 Maintain(right[x] , true);
47 Maintain(x , false);
48 Maintain(x , true);
49 }
50
51 void insert(int &x, int delta) {
52 if(!x) {
53 x = ++ NEW;
54 size[x] = 1;
55 key[x] = delta;
56 } else {
57 size[x] ++;
58 if(key[x] > delta)
59 insert(left[x] , delta);
60 else
61 insert(right[x] , delta);
62 Maintain(x , delta >= key[x]);
63 }
64 }
65
66 int Delete(int &x, int delta)
67 {
68 if(!x) return 0;
69 size[x] --;
70 if(delta == key[x] || (delta < key[x] && !left[x]) || (delta > key[x] && !right[x]) )
71 {
72 if(left[x] && right[x]) {
73 int p = Delete(left[x] , delta + 1);
74 key[x] = key[p];
75 return p;
76 } else {
77 int p = x;
78 x = left[x] + right[x];
79 return p;
80 }
81 } else {
82 if(delta < key[x])
83 Delete(left[x] , delta);
84 else
85 Delete(right[x] , delta);
86 }
87 }
88
89
90 int select_max(int &x, int k)
91 {
92 if(!x) return -1;
93 int r = size[ right[x] ] + 1;
94 if(r < k)
95 select_max(left[x] , k - r);
96 else if(r > k)
97 select_max(right[x] , k);
98 else
99 return key[x];
100 }
101
102 int select_min(int &x, int k) {
103 if(!x) return -1;
104 int l = size[ left[x] ] + 1;
105 if(l < k)
106 select_min(right[x] , k - l);
107 else if(l > k)
108 select_min(left[x] , k);
109 else
110 return key[x];
111 }
112
113 int ans[maxn];
114 struct NODE { int u, v, k, id; } A[maxn];
115
116 bool operator < (const NODE x, const NODE y)
117 {
118 if(x.u == y.u)
119 return x.v < y.v;
120 return x.u < y.u;
121 }
122
123 int main()
124 {
125 NEW = 0;
126 scanf("%d %d", &n, &m);
127 int root = 0;
128
129 for(int i=1; i