题目描述
不知道已经成为大学生的你是否还记得中位数这个东西，我们似乎很少再用到它，今天JM就想让你做一下这个小学数学题。
初始你手里什么也没有，接下来JM会按顺序给你(n)个数。当你手中的数的个数为奇数时，你需要告诉JM你手里这堆数的中位数是多少。
输入格式
第一行一个正整数(n)，表示给你的数的个数。
接下来一行(n)个整数，表示依次给你的这些数(a_i)。
输出格式
输出(x)行，每行一个整数，表示答案。
当(n)为奇数时(x=(n+1)/2)，当(n)为偶数时(x=n/2)，其中除法为下取整。
数据范围与提示
(1leq n leq 2*10^5)
(a_i leq 10^9)
思路
显然，我们可以建一个大根堆，保存前半部分数，一个小根堆，保存后半部分数，可以解决这个问题。
然而，关键词：动态，第k大，是不是想到了什么？对，平衡树！正好我最近在学习（chaoxi）fhq Treap，所以就拿这题当板子来练练手。
#include <cstdlib>
#include <algorithm>
#define maxn (int)(2 * 1e5 + 10)
using namespace std;
struct node {
int lson, rson, val, key, size;
} tree[maxn];
int cnt = 0, R = 0;
void update(int x) { tree[x].size = tree[tree[x].lson].size + tree[tree[x].rson].size + 1; }
void split(int root, int v, int &x, int &y) {
if (!root)
x = y = 0;
else {
if (v <= tree[root].val) {
x = root;
split(tree[root].rson, v, tree[root].rson, y);
} else {
y = root;
split(tree[root].lson, v, x, tree[root].lson);
}
update(root);
}
}
int merge(int x, int y) {
if (!x || !y)
return x + y;
if (tree[x].key <= tree[y].key) {
tree[x].rson = merge(tree[x].rson, y);
update(x);
return x;
} else {
tree[y].lson = merge(x, tree[y].lson);
update(y);
return y;
}
}
int add(int x) {
tree[++cnt].val = x;
tree[cnt].lson = tree[cnt].rson = 0;
tree[cnt].size = 1;
tree[cnt].key = rand();
return cnt;
}
int kth(int x, int k) {
if (tree[tree[x].lson].size + 1 == k)
return tree[x].val;
if (tree[tree[x].lson].size + 1 > k)
return kth(tree[x].lson, k);
else
return kth(tree[x].rson, k - tree[tree[x].lson].size - 1);
}
int main() {
int i, n, x, y, a, ans;
srand(19260817);
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d", &a);
split(R, a, x, y);
R = merge(merge(x, add(a)), y);
if (i & 1) {
ans = kth(R, i + 1 >> 1);
printf("%d
", ans);
}
}
return 0;
}