P12570 [UOI 2023] An Array and Medians of Subarrays

· · 题解

Solution

这题有一个很重要的一点，就是最多分成两个序列。如果存在分成多个序列的解，那么一定可以合并变成两个。

对于多个中位数相同的序列 a，令这个中位数位置为 pos，每个序列排序之后，pos 右边的数都大于等于 a_{pos}，左边的数都小于等于 a_{pos}，且这两个值一定相等。序列合并排序后这两个值分别求和，两边仍然相等，故中位数相等（拙劣的证明）。

于是题目变成了，把一个序列分成两个，使其中位数相等。考虑枚举分割线，判断左右两边的中位数是否相等。

Specifically

中位数可以预处理，因为我们只需要前缀与后缀数组的中位数。从前往后遍历，先把当前位置的数加进去，然后求第 k 小。那做法可太多了。由于我太菜了不会可持久化线段树，还是用平衡树吧。后缀的预处理同理。

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>
#define lson tr[root].ls
#define rson tr[root].rs

const int MAXN = 2e5 + 10;

struct node {
    int ls, rs, sz, val, key;
    node () {
        ls = rs = sz = val = key = 0;
    }
};

struct fanhaoqiang {
public:
    std::vector <node> tr; int allroot, tot;

    fanhaoqiang () {
        allroot = tot = 0;
        tr.resize(1);
    }

private:
    int newnode (int val) {
        tr.push_back(node());
        tr[++tot].val = val;
        tr[tot].sz = 1;
        tr[tot].key = rand();
        return tot;
    }

    void split (int root, int &l, int &r, int val) {
        if (root == 0) {
            l = r = 0;
            return;
        }
        else if (tr[root].val <= val) {
            l = root;
            split(rson, rson, r, val);
        }
        else {
            r = root;
            split(lson, l, lson, val);
        }
        push_up(root);
    }

    void push_up (int root) {
        tr[root].sz = tr[lson].sz + tr[rson].sz + 1;
    }

    int merge (int l, int r) {
        if (!l || !r)
            return (l | r);
        else if (tr[l].key <= tr[r].key) {
            tr[l].rs = merge(tr[l].rs, r);
            push_up(l);
            return l;
        }
        else {
            tr[r].ls = merge(l, tr[r].ls);
            push_up(r);
            return r;
        }
    }

public:
    int rank_kth (int root, int k) {
        if (tr[root].sz < k) return -1;
        else if (tr[lson].sz + 1 == k) return tr[root].val;
        else if (tr[lson].sz >= k) return rank_kth(lson, k);
        else return rank_kth(rson, k - tr[lson].sz - 1);
    }

    void insert (int val) {
        int x, y;
        split(allroot, x, y, val - 1);
        allroot = merge(merge(x, newnode(val)), y);
    }
}twd, bwd; // toward,backward

int n, a[MAXN], pre[MAXN], suf[MAXN], flag;

int main () {
    std::cin >> n;

    for (int i = 1; i <= n; i++)
        std::cin >> a[i];

    pre[1] = a[1];
    twd.insert(a[1]);
    for (int i = 3; i <= n; i += 2) { //因为只能分成奇数长度，所以每次加 2
        twd.insert(a[i - 1]);
        twd.insert(a[i]);
        pre[i] = twd.rank_kth(twd.allroot, i / 2 + 1);
    }

    suf[n] = a[n];
    bwd.insert(a[n]);
    for (int i = n - 2; i >= 1; i -= 2) {
        bwd.insert(a[i]);
        bwd.insert(a[i + 1]);
        suf[i] = bwd.rank_kth(bwd.allroot, (n - i + 1) / 2 + 1);
    }

    for (int i = 1; i <= n; i += 2)
        if (pre[i] == suf[i + 1])
            flag = 1;

    if (flag) std::cout << "Yes";
    else std::cout << "No";

    return 0;
}

Other

但是这道题不管是主席树还是平衡树，都是蓝题，为什么这是一道绿题？

还有，这道题还可以跑得更快些。把范浩强换成红黑树就行。

由于篇幅以及洛谷剪贴板炸了，暂且放在这里。