题目链接：LOJ 2432

给定长度为 $n$ 的正整数序列 $p_i$。有 $m$ 组查询，每次查询区间 $[a,b]$ 中出现次数严格大于一半的数。

数据范围：$1\le n,m\le 5\times 10^5$，$1\le p_i\le n$。

Solution

我们考虑用主席树维护，在当前区间 $[l,r]$ 中，如果 $[l, mid]$ 的数字出现次数大于询问区间的一半，那么递归到左区间查询；反之如果右区间满足条件，那么递归到右区间查询；否则无解。

很显然，不可能左右区间同时满足条件，正确性得证。

时间复杂度：$\mathcal O(m\log n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 5e5 + 5;

int n, m, a[N], b[N];

struct Chairman {
    static const int M = 1e7 + 5;
    int idx, rt[N], ls[M], rs[M], sum[M];
    void build(int &p, int l, int r) {
        p = ++idx;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(ls[p], l, mid);
        build(rs[p], mid + 1, r);
    }
    void modify(int &p, int l, int r, int u, int x, int v) {
        p = ++idx, ls[p] = ls[u], rs[p] = rs[u], sum[p] = sum[u] + v;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(ls[p], l, mid, ls[u], x, v);
        } else {
            modify(rs[p], mid + 1, r, rs[u], x, v);
        }
    }
    int query(int p1, int p2, int l, int r, int len) {
        if (l == r) {
            return l;
        }
        int mid = (l + r) >> 1;
        int lsz = sum[ls[p2]] - sum[ls[p1]];
        int rsz = sum[rs[p2]] - sum[rs[p1]];
        if (2 * lsz > len) {
            return query(ls[p1], ls[p2], l, mid, len);
        }
        if (2 * rsz > len) {
            return query(rs[p1], rs[p2], mid + 1, r, len);
        }
        return 0;
    }
} cha;

int discretize() {
    for (int i = 1; i <= n; i++) {
        b[i] = a[i];
    }
    std::sort(b + 1, b + n + 1);
    int sz = std::unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = std::lower_bound(b + 1, b + sz + 1, a[i]) - b;
    }
    return sz;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int sz = discretize();
    cha.build(cha.rt[0], 1, sz);
    for (int i = 1; i <= n; i++) {
        cha.modify(cha.rt[i], 1, sz, cha.rt[i - 1], a[i], 1);
    }
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        int ans = cha.query(cha.rt[l - 1], cha.rt[r], 1, sz, r - l + 1);
        printf("%d\n", b[ans]);
    }
    return 0;
}