摩尔投票
方法：
大概操作就是记录一个 \(major,cnt\) ，顺序遍历数组 \(a\)，假设遍历到了第 \(i\) 个，当 \(cnt=0\) 时让 \(major=a_i\) ， 当 \(cnt\) 不为 \(0\) 时，如果 \(a_i=major\) 让 \(cnt\) 加 \(1\) ，否则减 \(1\)
这样做的时间复杂度是 \(O(n)\) 的，空间复杂度是 \(O(1)\) 的。
注意这个是有绝对众数的时候才是对的。
拓展：
现在你要求出现次数超过 \(\frac{n}{k}\) 的，显然数的个数是小于 \(k\) 的，不然 \(n\) 个肯定不够
其实做法和上面差不多，现在要开两个数组 \(major_i,cnt_i\)
操作：
首先如果 \(x\) 本身是候选者的话，则对其出现次数加一
如果不是的话，如果有 \(cnt=0\) 的位置那么就让 \(x\) 成为候选者，出现次数变为 \(1\)，否则让所有候选者出现次数减 \(1\)
注意这个不一定所有都是对的，但是正确的答案一定包括
这个万一就感觉有点抽象了，所以还是证明一下吧
考虑反证法，假设 \(x\) 出现了 \(y>\frac{n}{k}\) 次，但是他不在答案里面
- 他就没有进入过 \(major\) 数组：那么他肯定让所有候选者减去了 \(y\) 次，但是由 \(y>\frac{n}{k}\) 知 \(y\times k > n\) 不符合题意
- 他进入过然后被干掉了：同理，他被干掉了说明肯定所有候选者都减去了 \(y\) 次，同上，还是寄
那么摩尔投票有什么用呢？
摩尔投票具有结合律，可以用 \(ds\) 乱搞
这玩意就和线性基很像，就直接把一个插进另一个就行了
CF643G Choosing Ads
就是板子
更加神奇的东西
其实感觉和摩尔投票没啥关系了
假设我现在猜一手区间众数为 \(x\) ，现在就可以把等于 \(x\) 的设为 \(1\) ，否则设为 \(-1\) ，这样 \(\text{chk}\) 一个区间是否众数是 \(x\) 就可以 \(O(1)\) 了
因为是绝对众数，所以我枚举一遍我猜的众数就可以求出所有区间的众数了，但是这是 \(O(n^2)\) 的
但是还有性质
标签：Major,观后感,cnt,tv,绝对,mid,众数,区间,major From： https://www.cnblogs.com/lnyx/p/17390054.html