LOJ 104. 普通平衡树

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int N = 1e5 + 10;
  4 int n, opt, x, val[N], fa[N], sze[N], sum[N], lc[N], rc[N], T, rt;
  5 void pushup(int k) {
  6     sze[k] = sze[lc[k]] + sze[rc[k]] + sum[k];
  7 }
  8 void rot(int x) {
  9     int y = fa[x], z = fa[y];
 10     int b = (x == lc[y]) ? rc[x] : lc[x];
 11     fa[x] = z, fa[y] = x;
 12     if (b) fa[b] = y;
 13     if (z) (lc[z] == y ? lc[z] : rc[z]) = x;
 14     if (x == lc[y]) rc[x] = y, lc[y] = b;
 15     else lc[x] = y, rc[y] = b;
 16     pushup(y);
 17 }
 18 bool Wrt(int x) {
 19     return rc[fa[x]] == x;
 20 }    
 21 void Splay(int x, int tar) {
 22     while (fa[x] != tar) {
 23         if (fa[fa[x]] != tar) 
 24             Wrt(x) == Wrt(fa[x]) ? rot(fa[x]) : rot(x);
 25         rot(x);
 26     }
 27     if (!tar) rt = x;
 28     pushup(x);
 29 }
 30 void ins(int k) {//插入元素k 
 31     int x = rt, y = 0, d;
 32     while (x) {
 33         ++ sze[y = x];
 34         if (k == val[x]) {sum[x] ++; return ;}
 35         if (k < val[x]) x = lc[x], d = 0;
 36         else x = rc[x], d = 1;
 37     }
 38     x = ++ T; fa[x] = y; sze[x] = sum[x] = 1; val[x] = k;
 39     if (y) (d == 0 ? lc[y] : rc[y]) = x;
 40     Splay(x, 0);
 41 }
 42 int Rank(int k, bool f) { //按数值找   0：位置   1：排名
 43      int x = rt, ret = 0;
 44     while (x) {
 45         if (val[x] == k) return f ? ret + sze[lc[x]] + 1 : x;
 46         if (val[x] > k) x = lc[x];
 47         else ret += sze[lc[x]] + sum[x], x = rc[x]; 
 48     }    
 49     return f ? ret : 0;
 50 }
 51 int find(int k) {//按排名找 
 52     int x = rt;
 53     while (x) {
 54         if (sze[lc[x]] >= k) x = lc[x];
 55         else if (sze[lc[x]] + sum[x] >= k) return val[x];
 56         else k -= (sze[lc[x]] + sum[x]), x = rc[x];
 57     }
 58     return val[x];
 59 }
 60 void del(int k) {//删除元素k所在节点 
 61     int x = Rank(k, 0);
 62     Splay(x, 0);
 63     if (sum[x] > 1) {
 64         -- sze[x]; -- sum[x]; return ;
 65     }
 66     fa[lc[x]] = fa[rc[x]] = 0;
 67     if (!lc[x] || !rc[x]) rt = lc[x] + rc[x];
 68     else {
 69         int w = lc[x];
 70         while(rc[w]) w = rc[w];
 71         Splay(w, 0);
 72         rc[w] = rc[x]; fa[rc[x]] = w;
 73         pushup(w);
 74     }
 75 }
 76 int pre(int k) {//求前驱 
 77     int x = rt, ret = 0;
 78     while (x) {
 79         if (val[x] < k) ret = val[x], x = rc[x];
 80         else x = lc[x];
 81     }
 82     return ret;
 83 }
 84 int aft(int k) {//求后继 
 85     int x = rt, ret = 0;
 86     while (x) {
 87         if (val[x] > k) ret = val[x], x = lc[x];
 88         else x = rc[x];
 89     }
 90     return ret;
 91 }
 92 signed main() {        
 93     scanf("%d", &n);
 94     while (n --) {
 95         scanf("%d %d", &opt, &x);
 96         if (opt == 1) ins(x);
 97         if (opt == 2) del(x);
 98         if (opt == 3) cout << Rank(x,1) << '\n';
 99         if (opt == 4) cout << find(x) << '\n';
100         if (opt == 5) cout << pre(x) << '\n';
101         if (opt == 6) cout << aft(x) << '\n';
102     }    
103     return 0;
104 }