1 struct SBT{  2     int treeCnt, root;  3     struct tnode{int data, lc, rc, size;} tree[maxn];  4     inline void clear(){treeCnt = 0; root = 0;}  5     inline void leftRot(int &x){  6         int k = tree[x].rc;  7         tree[x].rc = tree[k].lc;  8         tree[k].lc = x;  9         tree[k].size = tree[x].size; 10         tree[x].size = tree[tree[x].lc].size + tree[tree[x].rc].size + 1; 11         x = k; 12     } 13     inline void rightRot(int &x){ 14         int k = tree[x].lc; 15         tree[x].lc = tree[k].rc; 16         tree[k].rc = x; 17         tree[k].size = tree[x].size; 18         tree[x].size = tree[tree[x].lc].size + tree[tree[x].rc].size + 1; 19         x = k; 20     } 21     void maintain(int &x, bool fg){ 22         if (!fg){ 23             if (tree[tree[tree[x].lc].lc].size > tree[tree[x].rc].size) 24                 rightRot(x); 25             else if (tree[tree[tree[x].lc].rc].size > tree[tree[x].rc].size){ 26                 leftRot(tree[x].lc); 27                 rightRot(x); 28             } 29             else return; 30         } 31         else{ 32             if (tree[tree[tree[x].rc].rc].size > tree[tree[x].lc].size) 33                 leftRot(x); 34             else if (tree[tree[tree[x].rc].lc].size > tree[tree[x].lc].size){ 35                 rightRot(tree[x].rc); 36                 leftRot(x); 37             } 38             else return; 39         } 40         maintain(tree[x].lc, 0); 41         maintain(tree[x].rc, 1); 42         maintain(x, 1); 43         maintain(x, 0); 44     } 45     void ins(int &x, int data){ 46         if (x == 0){ 47             x = ++treeCnt; 48             tree[x].lc = tree[x].rc = 0; 49             tree[x].size = 1; tree[x].data =http://www.mamicode.com/ data; 50         } 51         else{ 52             tree[x].size++; 53             ins((data < tree[x].data) ? (tree[x].lc) : (tree[x].rc), data); 54             maintain(x, data >= tree[x].data); 55         } 56     } 57     int del(int &x, int data){ 58         int tmp; 59         tree[x].size--; 60         if (data =http://www.mamicode.com/= tree[x].data || data < tree[x].data && tree[x].lc == 0 || data > tree[x].data && tree[x].rc == 0){ 61             tmp = tree[x].data; 62             if (tree[x].lc && tree[x].rc) 63                 tree[x].data = http://www.mamicode.com/del(tree[x].lc, tree[x].data + 1); 64             else 65                 x = tree[x].lc + tree[x].rc; 66         } 67         else if (data < tree[x].data) tmp = del(tree[x].lc, data); 68         else if (data > tree[x].data) tmp = del(tree[x].rc, data); 69         return tmp; 70     } 71     bool find(int x, int data){ 72         if (x == 0) return 0; 73         if (data < tree[x].data) return find(tree[x].lc, data); 74         else return (tree[x].data =http://www.mamicode.com/= data || find(tree[x].rc, data)); 75     } 76     int rank(int x, int data){ 77         if (x == 0) return 1; 78         if (data <= tree[x].data) return rank(tree[x].lc, data); 79         return rank(tree[x].rc, data) + tree[tree[x].lc].size + 1; 80     } 81     int select(int x, int k){ 82         int r = tree[tree[x].lc].size + 1; 83         if (k == r) return tree[x].data; 84         if (k < r) return select(tree[x].lc, k); 85         return select(tree[x].rc, k - r); 86     } 87     inline int getmin(){ 88         int x; 89         for (x = root; tree[x].lc; x = tree[x].lc); 90         return tree[x].data; 91     } 92     inline int getmax(){ 93         int x; 94         for (x = root; tree[x].rc; x = tree[x].rc); 95         return tree[x].data; 96     } 97     int pred(int x, int data){ 98         if (x == 0) return data; 99         if (data <= tree[x].data)100             return pred(tree[x].lc, data);101         else{102             int tmp = pred(tree[x].rc, data);103             if (tmp == data) tmp = tree[x].data;104             return tmp;105         }106     }107     int succ(int x, int data){108         if (x == 0) return data;109         if (tree[x].data <= data)110             return succ(tree[x].rc, data);111         else{112             int tmp = succ(tree[x].lc, data);113             if (tmp == data) tmp = tree[x].data;114             return tmp;115         }116     }117 } bst;