洛谷 P3871 [TJOI2010]中位数
Description
给定一个由N个元素组成的整数序列，现在有两种操作：
1 add a
在该序列的最后添加一个整数a，组成长度为N + 1的整数序列
2 mid 输出当前序列的中位数
中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）
例1：1 2 13 14 15 16 中位数为13
例2：1 3 5 7 10 11 17 中位数为7
例3：1 1 1 2 3 中位数为1
Input
- 第一行为初始序列长度N。第二行为N个整数，表示整数序列，数字之间用空格分隔。第三行为操作数M，即要进行M次操作。下面为M行，每行输入格式如题意所述。
Output
- 对于每个mid操作输出中位数的值
Sample Input
61 2 13 14 15 165add 5add 3midadd 20mid
Sample Output
513
Data Size
对于30%的数据，1 ≤ N ≤ 10,000，0 ≤ M ≤ 1,000
对于100%的数据，1 ≤ N ≤ 100,000，0 ≤ M ≤ 10,000
序列中整数的绝对值不超过1,000,000,000，序列中的数可能有重复
每个测试点时限1秒
题解：
- 平衡树。
- 双倍经验？？当时写这题跟这几乎一模一样的题时用的对顶堆算法。现在练习平衡树，就用平衡树A掉了。这题用平衡树很好理解，一个插入操作和查找第k大的操作。
#include#include #include #define N 100005#define inf 0x7fffffffusing namespace std;struct T {int l, r, val, dat, cnt, size;} t[N + 10005];int n, m, root, tot, sum;int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x *= f;}int New(int val){ t[++tot].val = val, t[tot].dat = rand(); t[tot].cnt = t[tot].size = 1; return tot;}void up(int p) {t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].cnt;}void zig(int &y){ int x = t[y].l; t[y].l = t[x].r, t[x].r = y, y = x; up(t[y].r), up(y);}void zag(int &x){ int y = t[x].r; t[x].r = t[y].l, t[y].l = x, x = y; up(t[x].l), up(x);}void insert(int &p, int val){ if(!p) {p = New(val); return;} if(val == t[p].val) {t[p].cnt++, up(p); return;} if(val < t[p].val) { insert(t[p].l, val); if(t[t[p].l].dat > t[p].dat) zig(p); } else { insert(t[p].r, val); if(t[t[p].r].dat > t[p].dat) zag(p); } up(p);}int valOfRank(int p, int rank){ if(!p) return inf; if(t[t[p].l].size >= rank) return valOfRank(t[p].l, rank); if(t[t[p].l].size + t[p].cnt >= rank) return t[p].val; return valOfRank(t[p].r, rank - t[t[p].l].size - t[p].cnt);}int main(){ New(inf), New(-inf), root = 1, t[1].l = 2, up(1); cin >> n, sum = n; for(int i = 1; i <= n; i++) insert(root, read()); cin >> m; for(int i = 1; i <= m; i++) { char c[5]; scanf("%s", c); if(c[0] == 'a') insert(root, read()), sum++; else if(c[0] == 'm') printf("%d\n", valOfRank(root, (sum + 1) / 2 + 1)); } return 0;}