P3567 [POI2014]KUR-Couriers

\(P3567\) [\(POI2014\)]\(KUR-Couriers\)

一、题目大意

给一个长度为 \(n\) 的正整数序列 \(a\)。共有 \(m\) 组询问，每次询问一个区间 \([l,r]\) ，是否存在一个数在 \([l,r]\) 中 出现的次数严格大于一半 。如果存在，输出这个数，否则输出 \(0\)。

\(1 \leq n,m \leq 5 \times 10^5,1 \leq a_i \leq n\)

二、解题思路

主席树入门题啦

主席树基础请先去打 模板题

题面大意就是给定一个区间\([l,r]\),让你求出一个数字\(x\)的出现次数大于\(\frac{r-l+1}{2}\)。

思路:出现次数大于一半而且是绝对的,如果左儿子的数字个数值已经大于\(\frac{r-l+1}{2}\),那么右儿子肯定小于\(\frac{r-l+1}{2}\)。也可能两边都等于\(\frac{r-l+1}{2}\) ,不过这样说明没有答案,返回\(0\)就行了。

如果左儿子(或者右儿子)的\(cnt\)值大于\(\frac{r-l+1}{2}\),那么答案肯定在左子树(或右子树)中,这样就可以\(log\ n\)的时间求出答案。

三、实现代码

#include <cstdio>
#include <algorithm>
using namespace std;

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
const int N = 5e5 + 10;
struct Node {
    int l, r, cnt;
} tr[N << 5];

int root[N], idx;
int n, m;

void insert(int &u, int l, int r, int x) {
    tr[++idx] = tr[u];
    tr[u].cnt++;
    u = idx;
    if (l == r) return;

    int mid = l + r >> 1;
    if (x <= mid)
        insert(tr[u].l, l, mid, x);
    else
        insert(tr[u].r, mid + 1, r, x);
}

int query(int p, int q, int l, int r, int x) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (2 * (tr[tr[q].l].cnt - tr[tr[p].l].cnt) > x)
        return query(tr[p].l, tr[q].l, l, mid, x);
    if (2 * (tr[tr[q].r].cnt - tr[tr[p].r].cnt) > x)
        return query(tr[p].r, tr[q].r, mid + 1, r, x);
    return 0;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P3567.in", "r", stdin);
#endif
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        int x = read();
        root[i] = root[i - 1];
        insert(root[i], 1, n, x);
    }

    while (m--) {
        int l = read(), r = read();
        printf("%d\n", query(root[l - 1], root[r], 1, n, r - l + 1));
    }
    return 0;
}