P7252 题解

namelessgugugu · 2022-09-08 09:55:47 · 题解

首先这题显然可以有一万种做法做到 O(n\log n) 的时间复杂度，但数据范围才 50000，为什么不用一点更劣但是更好写的做法呢？

考虑到如果区间有绝对众数，那么如果你随机挑选一个区间中的数，取到答案的概率超过 \frac{1}{2}。如果有答案，那么期望随机 O(1) 次就能找到，并且随机 k 次后还未找到答案的概率是不超过 (\frac{1}{2})^k 的，因此如果多随几次后还未找到答案，我们就可以认定该区间没有绝对众数。我在代码中把这个阈值定为了 40 次。

最后一个问题就是怎么算一个值在区间中的出现次数，这里直接选择用 vector 存下每一个颜色的序列，然后在对应颜色的 vector 中二分左右端点，下标之差即为出现次数。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <random>
const int N = 50005;
int n, m;
int c[N];
std::vector<int> vec[N];
inline int calc(int l, int r, int c)
{
    return std::upper_bound(vec[c].begin(), vec[c].end(), r) - std::lower_bound(vec[c].begin(), vec[c].end(), l);
}
std::mt19937 rng(114514);
int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n;++i)
        scanf("%d", c + i), vec[c[i]].push_back(i);
    for (int i = 1, l, r; i <= m;++i)
    {
        scanf("%d%d", &l, &r);
        int ans = 0;
        for (int j = 1; j <= 40; ++j)
        {
            int t = rng() % (r - l + 1) + l;
            int cnt = calc(l, r, c[t]);
            if(cnt * 2 > r - l + 1)
            {
                ans = c[t];
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}