Description
设计一种数据结构，支持元素的插入，查询当前元素的中位数
Solution
为了练习Splay，我决定用牛刀杀鸡，用Splay解决对顶堆的问题。
然后这就是一道Splay的模板题（简化简化再简化）
Code
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 2147483647; 4 struct Splay { 5 int sum, cnt, val; 6 int fa, ch[2]; 7 } a[100010]; 8 int n, m, root, tot, cnt; 9 inline int read() { 10 int ret = 0, op = 1; 11 char c = getchar(); 12 while (!isdigit(c)) { 13 if (c == '-') op = -1; 14 c = getchar(); 15 } 16 while (isdigit(c)) { 17 ret = ret * 10 + c - '0'; 18 c = getchar(); 19 } 20 return ret * op; 21 } 22 void update(int now) { 23 a[now].sum = a[a[now].ch[0]].sum + a[a[now].ch[1]].sum + a[now].cnt; 24 } 25 void connect(int x, int fa, int op) { 26 a[x].fa = fa; 27 a[fa].ch[op] = x; 28 } 29 void rotate(int x) { 30 int y = a[x].fa; 31 int z = a[y].fa; 32 int xson = a[y].ch[1] == x ? 1 : 0; 33 int yson = a[z].ch[1] == y ? 1 : 0; 34 int B = a[x].ch[xson ^ 1]; 35 connect(B, y, xson); connect(y, x, xson ^ 1); connect(x, z, yson); 36 update(y); update(x); 37 } 38 void splay(int from, int to) { 39 while (a[from].fa != to) { 40 int y = a[from].fa; 41 int z = a[y].fa; 42 if (z != to) 43 (a[y].ch[0] == from) ^ (a[z].ch[0] == y) ? rotate(from) : rotate(y); 44 rotate(from); 45 } 46 if (to == 0) root = from; 47 } 48 void insert(int val) { 49 int now = root, fa = 0; 50 while (now && a[now].val != val) fa = now, now = a[now].ch[val > a[now].val]; 51 if (now) a[now].cnt++; 52 else { 53 now = ++tot; 54 a[tot].val = val; 55 a[tot].fa = fa; 56 a[tot].sum = a[tot].cnt = 1; 57 a[tot].ch[0] = a[tot].ch[1] = 0; 58 if (fa) a[fa].ch[val > a[fa].val] = tot; 59 } 60 splay(now, 0); 61 } 62 int query(int k) { 63 int now = root; 64 while (1) { 65 if (k <= a[a[now].ch[0]].sum) now = a[now].ch[0]; 66 else if (k > a[a[now].ch[0]].sum + a[now].cnt) { 67 k -= a[a[now].ch[0]].sum + a[now].cnt; 68 now = a[now].ch[1]; 69 } 70 else return a[now].val; 71 } 72 } 73 int main() { 74 n = read(); 75 insert(-INF); insert(INF); 76 for (register int i = 1; i <= n; ++i) ++cnt, insert(read()); 77 m = read(); 78 char s[10]; 79 while (m--) { 80 scanf("%s", s); 81 if (s[0] == 'a') ++cnt, insert(read()); 82 else { 83 if (cnt & 1) printf("%d ", query(cnt / 2 + 1 + 1)); 84 else printf("%d ", min(query(cnt / 2 + 1), query(cnt / 2 + 1 + 1))); 85 } 86 } 87 return 0; 88 }