题解 P3871 【[TJOI2010]中位数】

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

核心代码(非常短)

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 函数当中,使用了位运算简化代码。代码等价于:

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 快一些)

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));
    }
}