过程

如果给你一个长度为 $n$ 的序列，如何空间复杂度 $O(1)$ 求出这个序列中出现次数严格大于 $\frac{n}{2}$ 的数？

摩尔投票算法就是来解决这一类问题的，本质是每次选择序列中两个不同的数，然后消除，消除到找不到两个不同的数为止，剩下的即为答案。

因为如果要消除完，那么需要消除 $\lfloor \frac{n}{2} \rfloor$ 次，而如果一个数出现次数大于 $\frac{n}{2}$，那么这个数一定不会被删除。

注意如果区间中不存在这样的数，摩尔投票可能会给出一个错误的答案。

int nw, cnt = 0;
for (int i : a) {
    if (i == nw) cnt ++ ;
    else {
        if (cnt == 0) nw = i, cnt = 1;
        else cnt -- ;
    }
}

我们拓展一下，如果是求序列中严格大于 $\frac{n}{k}$ 的数，同理，每次消除 $k$ 个数，最多消除 $\lfloor \frac{n}{k} \rfloor$ 次。

于是同样有如上做法。

例题

CF643G. Choosing Ads

是用线段树维护每个区间进行摩尔投票后剩下的数即可，复杂度 $O(nk^2\log n)$。