zoj 2112 Dynamic Rankings(SBT in SegTree)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1112
　　这题以前我曾经是用k大数DC搜过去的，每次k大前都复制区间，理论上那是必然超时的。今天我用线段树套SBT过了这题，不过其实用树套树做，最后还是要二分结果区间来得到最终的结果，复杂度是O(nlognlogn)。最近看了可持续化数据结构的论文，这题用可持续化线段树可以使代码更简单，内存消耗更小，虽然复杂度貌似没有变。
　　这题建立多棵平衡树以后，在使用完以后必须销毁，不然会MLE的！
代码如下：
View Code
  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <algorithm>
  4 
  5 using namespace std;
  6 
  7 const int inf = 0x7f7f7f7f;
  8 const int maxn = 50001;
  9 struct SBTNode {
 10     int size, key;
 11     SBTNode *c[2];
 12 
 13     SBTNode(int k = 0) {
 14         key = k;
 15         size = 1;
 16         c[0] = c[1] = NULL;
 17     }
 18 } ;
 19 struct SBTree {
 20     SBTNode *Root;
 21 
 22     SBTree() {
 23         Root = NULL;
 24     }
 25 
 26     void delTreeMain(SBTNode *&rt) {
 27         if (!rt) return ;
 28         delTreeMain(rt->c[0]);
 29         delTreeMain(rt->c[1]);
 30         delete rt;
 31         rt = NULL;
 32     }
 33 
 34     void delTree() {
 35         delTreeMain(Root);
 36     }
 37 
 38     void rotate(SBTNode *&x, bool left) {
 39         bool right = !left;
 40         SBTNode *y = x->c[left];
 41 
 42         x->c[left] = y->c[right];
 43         y->c[right] = x;
 44         y->size = x->size;
 45 
 46         x->size = (x->c[0] ? x->c[0]->size : 0) + (x->c[1] ? x->c[1]->size : 0) + 1;
 47         x = y;
 48     }
 49 
 50     int getPosMain(int key, SBTNode *rt) {
 51         if (!rt) return 0;
 52 
 53         int k = rt->key;
 54 
 55 //        if (key == k) return rt->c[0] ? rt->c[0]->size : 0;
 56         if (key <= k) return getPosMain(key, rt->c[0]);
 57         else return getPosMain(key, rt->c[1]) + (rt->c[0] ? rt->c[0]->size : 0) + 1;
 58     }
 59 
 60     int getPos(int key) {
 61         return getPosMain(key, Root);
 62     }
 63 
 64     void maintain(SBTNode *&rt, bool right) {
 65         if (!rt->c[right] || !rt) return ;
 66 
 67         bool left = !right;
 68         int ls = rt->c[left] ? rt->c[left]->size : 0;
 69 
 70         if (rt->c[right]->c[right] && rt->c[right]->c[right]->size > ls) {
 71             rotate(rt, right);
 72         } else if (rt->c[right]->c[left] && rt->c[right]->c[left]->size > ls) {
 73             rotate(rt->c[right], left);
 74             rotate(rt, right);
 75         } else return ;
 76 
 77         maintain(rt->c[0], false);
 78         maintain(rt->c[1], true);
 79         maintain(rt, false);
 80         maintain(rt, true);
 81     }
 82 
 83     void insMain(SBTNode *&rt, SBTNode *x) {
 84         if (!rt) {
 85             rt = x;
 86             return ;
 87         }
 88         rt->size++;
 89         if (x->key < rt->key) insMain(rt->c[0], x);
 90         else insMain(rt->c[1], x);
 91         maintain(rt, x->key >= rt->key);
 92     }
 93 
 94     void ins(SBTNode *x) {
 95         insMain(Root, x);
 96     }
 97 
 98     void ins(int x) {
 99         SBTNode *tmp = new SBTNode(x);
100 
101         insMain(Root, tmp);
102     }
103 
104     void delMain(SBTNode *&rt, int key) {
105         if (!rt) return ;
106         rt->size--;
107         if (key < rt->key) {
108             delMain(rt->c[0], key);
109         } else if (key > rt->key) {
110             delMain(rt->c[1], key);
111         } else {
112             SBTNode *t;
113 
114             if (!rt->c[0] && !rt->c[1]) {
115                 delete rt;
116                 rt = NULL;
117             } else if (!rt->c[1]) {
118                 t = rt;
119                 rt = rt->c[0];
120                 delete t;
121             } else if (!rt->c[0]) {
122                 t = rt;
123                 rt = rt->c[1];
124                 delete t;
125             } else {
126                 t = rt->c[1];
127                 while (t->c[0]) t = t->c[0];
128                 rt->key = t->key;
129                 delMain(rt->c[1], t->key);
130             }
131         }
132     }
133 
134     void del(int k) {
135         delMain(Root, k);
136     }
137 
138     void printMain(SBTNode *rt) {
139         if (!rt) return ;
140         printMain(rt->c[0]);
141         printf("%d ", rt->key);
142         printMain(rt->c[1]);
143     }
144 
145     void print() {
146         printMain(Root);
147         puts("~~~");
148     }
149 } sbt[maxn << 2];
150 
151 int rec[maxn];
152 #define lson l, m, rt << 1
153 #define rson m + 1, r, rt << 1 | 1
154 
155 void build(int l, int r, int rt) {
156     sbt[rt] = SBTree();
157     if (l == r) {
158         return ;
159     }
160     int m = (l + r) >> 1;
161 
162     build(lson);
163     build(rson);
164 }
165 
166 void unbuild(int l, int r, int rt) {
167     sbt[rt].delTree();
168     if (l == r) {
169         return ;
170     }
171     int m = (l + r) >> 1;
172 
173     unbuild(lson);
174     unbuild(rson);
175 }
176 
177 void ins(int pos, int key, int l, int r, int rt) {
178     sbt[rt].ins(key);
179     if (l == r) {
180         return ;
181     }
182     int m = (l + r) >> 1;
183 
184     if (pos <= m) {
185         ins(pos, key, lson);
186     } else {
187         ins(pos, key, rson);
188     }
189 }
190 
191 void repMain(int pos, int key, int l, int r, int rt) {
192     sbt[rt].del(rec[pos]);
193     sbt[rt].ins(key);
194     if (l == r) {
195         return ;
196     }
197     int m = (l + r) >> 1;
198 
199     if (pos <= m) {
200         repMain(pos, key, lson);
201     } else {
202         repMain(pos, key, rson);
203     }
204 }
205 
206 void rep(int pos, int key, int N) {
207     repMain(pos, key, 1, N, 1);
208     rec[pos] = key;
209 }
210 
211 int count(int key, int L, int R, int l, int r, int rt) {
212     if (L <= l && r <= R) {
213         return sbt[rt].getPos(key);
214     }
215     int m = (l + r) >> 1;
216     int ret = 0;
217 
218     if (L <= m) ret += count(key, L, R, lson);
219     if (m < R) ret += count(key, L, R, rson);
220 
221     return ret;
222 }
223 
224 int DC(int L, int R, int N, int k) {
225     int low = -1, high = 1000000001;
226     int m;
227 
228     while (low + 1 < high) {
229         m = (low + high) >> 1;
230         if (count(m, L, R, 1, N, 1) < k) low = m;
231         else high = m;
232     }
233 
234     return low;
235 }
236 
237 int main() {
238     int T, n, m;
239     int a, b, c;
240     char buf[3];
241 
242 //    freopen("in", "r", stdin);
243     scanf("%d", &T);
244     while (T--) {
245         scanf("%d%d", &n, &m);
246         build(1, n, 1);
247         for (int i = 1; i <= n; i++) {
248             scanf("%d", &rec[i]);
249             ins(i, rec[i], 1, n, 1);
250         }
251 //        printf("?? %d\n", count(2, 1, 3, 1, n, 1));
252         while (m--) {
253             scanf("%s", buf);
254             if (buf[0] == 'Q') {
255                 scanf("%d%d%d", &a, &b, &c);
256                 printf("%d\n", DC(a, b, n, c));
257             } else {
258                 scanf("%d%d", &a, &b);
259                 rep(a, b, n);
260             }
261         }
262         unbuild(1, n, 1);
263     }
264     /**** test SBTree ****
265         sbt[0] = SBTree();
266         for (int i = 0; i < 10; i++) {
267             scanf("%d", &x);
268             sbt[0].ins(x);
269     //        sbt[0].print();
270     //        puts("yeah~");
271         }
272         sbt[0].print();
273         for (int i = 0; i < 5; i++) {
274             scanf("%d", &x);
275             printf("%d\n", sbt[0].getPos(x));
276         }
277         for (int i = 0; i < 3; i++) {
278             scanf("%d", &x);
279             sbt[0].del(x);
280             sbt[0].print();
281         }
282     **********************/
283 
284     return 0;
285 }
——written by Lyon