题解 P3871 【[TJOI2010]中位数】
Anguei
2018-11-06 17:28:46
这类问题的最经典解法应当是对顶堆。动态维护一个序列使其有序，可以使用平衡树。
然而我不会平衡树，所以只能用 stl 代替平衡树了 QωQ。
这种简单的序列维护问题可以使用 stl 当中的 `vector` 以及 `lower_bound` 解决。下面来分析一下这道题的做法。
1. 首先，读入这个序列，并对其排序。排序后才可以根据下标 $O(1)$ 得出中位数。
2. 对于每个 `add` 操作，在序列中第一个大于等于 `a` 的元素的位置插入新数字。由于序列是有序的，所以可以**使用 `lower_bound`** 确定插入位置。
3. 对于每个 `mid` 操作，$O(1)$ 输出中位数即可。注意 `vector` 下标从零开始。
在洛谷上，最慢的测试点跑了 83ms：https://www.luogu.org/record/show?rid=13269424
### 核心代码（非常短）
```cpp
std::vector<int> v;
int query() {
return v[v.size() / 2 - (v.size() & 1 ^ 1)];
}
void add(int x) {
v.insert(std::lower_bound(v.begin(), v.end(), x), x);
}
int main() {
int n = read(); // read 是快读
while (n--) v.push_back(read());
std::sort(v.begin(), v.end());
int m = read();
while (m--) {
char opt[5]; scanf("%s", opt);
if (opt[0] == 'm') println(query(v)); // println 是快写
else add(read());
}
}
```
在上述代码的 `query` 函数当中，使用了位运算简化代码。代码等价于：
```cpp
int query() {
if (v.size() & 1) return v[v.size() / 2];
else return v[v.size() / 2 - 1];
}
```
----
## 20181118 更新
学了一下 Tarjan 的 Zip Tree。贴一个 Zip Tree 解法核心代码。（比 stl 快一些）
```cpp
struct Node {
int key, rank, size;
Node *lson, *rson;
Node() {}
Node(int x, int rank);
} NIL, *root = &NIL;
Node::Node(int x, int rank) : key(x), rank(rank), size(1), lson(&NIL), rson(&NIL) {}
Node *maintain(Node *o) {
o->size = 1 + o->lson->size + o->rson->size;
return o;
}
Node *insert(int x, int rank, Node *o) {
if (o == &NIL) return root = new Node(x, rank);
if (x <= o->key) {
Node *p = insert(x, rank, o->lson);
if (p->rank > o->rank) o->lson = p->rson, p->rson = maintain(o), o = p;
else o->lson = p;
} else {
Node *p = insert(x, rank, o->rson);
if (p->rank > o->rank) o->rson = p->lson, p->lson = maintain(o), o = p;
else o->rson = p;
}
return root = maintain(o);
}
Node *zip(Node *l, Node *r) {
if (l == &NIL) return r;
if (r == &NIL) return l;
if (l->rank < r->rank) {
r->lson = zip(l, r->lson);
return maintain(r);
} else {
l->rson = zip(l->rson, r);
return maintain(l);
}
}
Node *del(int x, Node *o) {
if (o->key == x) return root = zip(o->lson, o->rson);
if (o->key > x) o->lson = del(x, o->lson);
else o->rson = del(x, o->rson);
return root = maintain(o);
}
int findKth(int k, Node *o) {
if (o->lson->size == k - 1) return o->key;
else if (o->lson->size > k - 1) return findKth(k, o->lson);
else return findKth(k - o->lson->size - 1, o->rson);
}
void solution() {
std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
srand(time(nullptr));
int n = read(); rep(i, 1, n) insert(read(), rand() % jzm, root);
int Q = read(); while (Q--) {
std::string opt; std::cin >> opt;
if (opt[0] == 'a') insert(read(), rand() % jzm, root), ++n;
else println(findKth(n / 2 - (n & 1 ^ 1) + 1, root));
}
}
```