BLAST.tv Paris Major 2023 观后感
摩尔投票
方法：
大概操作就是记录一个 \(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
就是板子
code
更加神奇的东西
其实感觉和摩尔投票没啥关系了
假设我现在猜一手区间众数为 \(x\) ，现在就可以把等于 \(x\) 的设为 \(1\) ，否则设为 \(-1\) ，这样 \(\text{chk}\) 一个区间是否众数是 \(x\) 就可以 \(O(1)\) 了
因为是绝对众数，所以我枚举一遍我猜的众数就可以求出所有区间的众数了，但是这是 \(O(n^2)\) 的
但是还有性质 😍😍😍
- 当区间 \([l,r]\) 有绝对众数 \(x\) 时，区间 \([l,k],[k+1,r],k\in[l,r)\) 肯定有一个的有绝对众数并且他是 \(x\)
废话 - 区间 \([l,l],[l,l+1],[l,l+2],…,[l,r]\) 的本质不同绝对众数个数只有 \(log_2\) 个，原因是我要是想成为绝对众数要大于区间一半，就比如假设现在序列长度为 \(n\) ，你至少要加 \(n+1\) 个数才能成为新的绝对众数
将上面两个结合起来后，就有了一个非常 😎 的结论，就是跨过区间 \([l,r]\) 中点 \(mid\) 的所有区间的绝对众数个数是 \(\log\) 级别的，具体来说，根据性质 \(1\)，就是区间 \([l,l],[l,l+1],…,[l,mid]\) 和 \([mid,mid],[mid,mid+1],…,[mid,r]\) 的绝对众数集合一定是包含所有上述区间的绝对众数的，又根据性质 \(2\) ，可以知道只有 \(\log\) 个