2021-04-20

区间众数

通用求众数离线做法: 离散化之后, 开线段树维护数出现的频率的最大值, 带单点修改, 然后再用莫队, 移动区间时就跑一个单点修改, 复杂度是 $O(n\sqrt{n}\log n)$ 。

当只需要找频数超过一半的区间众数的时候, 可以这样考虑: 众数频数如果超过区间长度的一半, 那么任意划分区间为两段, 它必然要么在左半边超过一半, 要么在右边超过一半。然后就可以用线段树维护了。具体来说, 每个结点维护当前区间的众数及其频数。当合并时, 找左儿子和右儿子的众数。如果众数频数超过一半, 那么众数一定是二者之一。离散化后对每个数开一个pos数组维护出现位置, 在这个数组中二分得到这两者 (左右儿子的众数) 在当前区间中出现的频数, 取最大者即可。这样维护出来不一定是真区间众数, 但是如果众数超过区间长度一半, 那他一定维护这个众数。这个复杂度是每次查询 $O(\log^2n)$ 的。上面的论述中 “一半” 大概也可以改为其他比例, 这带来的问题是满足其他比例的众数可能有多个, 而这个比例超过一半时可以保证这样的众数唯一。

还有一种做法是随机化, 在待查询区间里找30个数作为候选众数, 对每个数检查它是否满足频数超过区间长度一半, 用上段的方法可以做到 $O(\log n)$ 查询。如果一个数频数超过区间长度一半, 那么在区间内任取30个数 (带放回) 找不到该众数的概率不超过 $2^{-30}$ 。这个做法完全可以扩展到其他比例, 比例变小时只需提高30这个常数, 例如要求众数频数超过 $$1/5$$ 时可以取100个候选众数, 即可做到 $({4\over 5})^{100}\approx2\times10^{-10}$ 概率。这是选不到真众数的概率, 因为超过1/5的众数可能有多个, 似乎有点迷惑 (选不到假众数的概率也是一样的, 他们互不影响) 。但是没关系, 由于候选众数中几乎必有真众数, 即使找到了假众数, 还需要和真众数比频数, 所以这种算法几乎必然找到真众数。

CF716Div2 D AC代码:

#include <bits/stdc++.h>
#define N 300000
using namespace std;
typedef pair<int, int> pii;
int n, m, maxn, a[N + 5];
struct node {
    int l, r, mx, aa;
};
node xds[4 * N+5];
vector<int> pos[N+5];

int cnt(int x, int l, int r) {
    int ret = upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l);
    return ret;
}

void build(int id, int l, int r) {
    if(l == r) {
        xds[id].l = xds[id].r = l;
        xds[id].mx = 1;
        xds[id].aa = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    xds[id].l = l; xds[id].r = r;
    if (cnt(xds[id * 2].aa, l, r) > cnt(xds[id * 2 + 1].aa, l, r)) {
        xds[id].mx = cnt(xds[id * 2].aa, l, r);
        xds[id].aa=  xds[id * 2].aa;
    } else {
        xds[id].mx = cnt(xds[id * 2 + 1].aa, l, r);
        xds[id].aa=  xds[id * 2 + 1].aa;
    }
}

pii get(int id, int l, int r) {
    // (frequency, value)
    pii ret, ret2;
    int f1 = 0, f2 = 0;
    if (l <= xds[id].l && xds[id].r <= r) {
        return pii(xds[id].mx, xds[id].aa);
    }
    int mid = (xds[id].l + xds[id].r) >> 1, rl = max(l, xds[id].l), rr = min(r, xds[id].r);
    if (l <= mid) {
        ret = get(id * 2, l, r);
        f1 = cnt(ret.second, rl, rr);
    }
    if (r > mid) {
        ret2 =  get(id * 2 + 1, l, r);
        f2 = cnt(ret2.second, rl, rr);
    }
    if (f1 > f2) {
        return pii(f1, ret.second);
    } else {
        return pii(f2, ret2.second);
    }
}

int main() {
    int l, r;
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        pos[i].push_back(n + 1);
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        pii most = get(1, l, r);
        cout << max(1, 2 * most.first - (r - l + 1)) << '\n';
    }
    return 0;
}

Wilson's blog