自动搬运

查看原文

来自洛谷，原作者为

	namelessgugugu 我是垃圾

搬运于2025-08-24 22:28:05，当前版本为作者最后更新于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;
}