【数学】摩尔投票

m摩尔投票是解决绝对众数的算法。

其实好像也不完全算数学…但就归给数学吧。以前见过但没写过题，力扣每日一题惊到我了居然真的有题…

概念

绝对众数：在一个集合中，某一个元素的出现次数比其他所有元素的出现次数之和还多，这个元素就为这个集合的绝对众数。

即，绝对众数的出现次数大于集合元素数的一半。

普通摩尔投票

原理很简单，扫一遍数组，用m记当前考虑的绝对众数，维护cnt，每遇到m就cnt++，否则cnt--。每扫一个新数时，如果cnt=0就说明先前的区间里的m已经没有优势，所以新数可以成为绝对众数的候选，将m改为新数。

int m = 0, cnt = 0;
for (int i = 0; i < n; ++i)
{
    if (cnt == 0)
        m = a[i];
    if (m == a[i])
        cnt++;
    else
        cnt--;
}

但这个算法得出来的m不一定是绝对众数（一个集合可能没有绝对众数），一定要验证，原理简单写一下：

设$index_i=\{x|a_x=i\}$ ，即保存数的下标集合，为了验证数$m$ 是否为绝对众数，只需检查集合$index_i$ 的大小是否大于数组长度的一半即可。

拓展摩尔投票

选出$k$ 个数，每个数的个数都超过集合总元素数的$\frac{1}{k+1}$ 。

int m[N], cnt[N];
for (auto e : nums) {
    int i = find(m, m + N, e) - m;
    if (i != N) { // 是候选
        cnt[i]++;
        continue;
    }
    int j = find(cnt, cnt + N, 0) - cnt;
    if (j != N) { // 存在一个位置可以称为新的候选
        m[j] = e;
        cnt[j] = 1;
        continue;
    }
    for (auto &c : cnt) // 既不是候选又不能成为新的候选，每个候选的cnt都要-1
        c--;
}

同样也需要验证每个数。

区间绝对众数

线段树建树$O(n)$ ，线段树查询$O(\log n)$ ，区间绝对众数验证$O(log n)$ 。

考虑线段树的两个节点，分别记录了一个区间的cnt和m，那么两个区间合并时，如果两边的m相同，那cnt直接相加即可；否则取cnt大的一边的m作为大区间的m，子区间cnt差绝对值作为大区间的cnt：

struct Node {
    int m, cnt;
    Node operator + (const Node& rhs) const {
        if(m == rhs.m) 
            return {m, cnt + rhs.cnt};
        if(cnt > rhs.cnt)
            return {m, cnt - rhs.cnt};
        return {rhs.m, rhs.cnt - cnt};
    }
};

在定义了节点加法运算后，线段树写起来就非常普通了，这里不贴代码了。

对于区间$[l,r]$ ，线段树求得$m$ ，$index$ 数组定义同普通摩尔投票，那么区间中$m$ 的个数可以这样求：

int count_seg(int m,int l,int r) {
    return upper_bound(cnt[rt].begin(), cnt[rt].end(), r) 
        - upper_bound(cnt[rt].begin(), cnt[rt].end(), l - 1);
}

只要验证个数大于区间的一半即可：

count_seg(m, l, r) >= (r - l + 1) * 2