Misra–Gries 算法/扩展摩尔投票

· · 个人记录

Misra-Gries 算法是对摩尔投票的拓展。
摩尔投票只能找出绝对众数，即占比严格大于 \dfrac12 的数。而 Misra-Gries 算法能够找出所有占比严格大于 \dfrac1k 的数（显然这种数最多有 k-1 个）。

为了更好的理解 Misra-Gries 算法，我们首先回忆一下摩尔投票（为了方便类比做了一定修改）：

模仿摩尔投票，我们推测 Misra-Gries 算法的过程如下：

感性理解就是删除 k 个不同的数后 \dfrac{n}k 减少了 1，而且因为 k 个数互不相同每个数出现次数最多减少 1，所以原先出现次数 >\dfrac{n}k 的删除后出现次数依然 >\dfrac{n'}k。

稍微证明一下顺便方便后面的一些推论：

定义一个数组 a 的 \text{k-reduction} 为每次从数组 a 中删除 k 个互不相同元素，直到无法删除为止的结果。显然，一个数组的 \text{k-reduction} 中至多有 k-1 种不同的元素。

Lemma 1. 将 a 和 b 的 \text{k-reduction} 拼接后再求 \text{k-reduction}，和对 a 和 b 的拼接求 \text{k-reduction} 等效。（由 \text{k-reduction} 定义易得）

定义一个元素 x 是一个长为 n 的数组 a 的 \text{k-heavy} 值，当且仅当 x 在 a 中出现次数 c_x 严格大于 \dfrac{n}k。

Theorem 1. 所有 a 的 \text{k-heavy} 元素都被 a 的 \text{k-reduction} 所包含。

证明：
不妨假设存在一个 a 的 \text{k-heavy} 元素 x 未在 a 的 \text{k-reduction} 中出现，那么根据 \text{k-reduction} 的定义，x 一定被删除了 c_x 次。
又因为每次均会删除 k 个不同的元素，所以一共删除了 kc_x 个元素。但是由于 c_x > \dfrac{n}k，可得删除的元素数量 kc_x>n，显然矛盾。
故假设不成立，即所有 a 的 \text{k-heavy} 元素都被 a 的 \text{k-reduction} 所包含。

称一个数组的 \text{k-reduction} 为一个 summary，并定义 reduce(a) 为 a 的 \text{k-reduction}，且两个 summary 相等当且仅当它们对应的数组中的 \text{k-heavy} 值相同。

由 Lemma 1 有 reduce(reduce(a)+reduce(b))=reduce(a+b)，那么定义两个 summary a,b 的和为 reduce(a+b)，则：

（均可由 Lemma 1 证明）

根据这个性质我们得到了可以用线段树维护 summary。

证明和性质时间结束，现在是幻想时间代码时间

int k;
//插入一个数 x
void ins_one(summary &a,int x)
{
    for(int i=0;i<k-1;i++) if(a.val[i]==x)
    {a.cnt[i]++; return;}
    for(int i=0;i<k-1;i++) if(!a.cnt[i])
    {a.val[i]=x; a.cnt[i]=1; return;}
    for(int i=0;i<k-1;i++) a.cnt[j]--;
}
summary reduce(vector<int> a)
{
    summary ans;
    for(int i=0;i<k-1;i++) ans.val[i]=-1,ans.cnt[i]=0;
    for(int i:a) ins_one(a,i);
    return ans;
}

该代码能以 O(nk) 的时间求出一个长为 n 的数组的 \text{k-reduction}。

一般 OI 里很少用到只求一次 reduce 的，因为 \text{k-heavy} 一般都能接受 O(n \log n) 排序求或者 O(n) 空间开桶求。所以比较常用的是合并两个 summary（复杂度 k^2）：

int k;
//插入 v 个 x，脑子里模拟一下跑 k 次 ins_one 代码应该很显然
void ins(summary &a,int x,int v)
{
    for(int i=0;i<k-1;i++) if(a.val[i]==x)
    {a.cnt[i]+=v; return;}
    for(int i=0;i<k-1;i++) if(!a.cnt[i])
    {a.val[i]=x; a.cnt[i]=v; return;}
    int mn=v;
    for(int i=0;i<k-1;i++) if(a.cnt[i]<mn) mn=a.cnt[i];
    for(int i=0;i<k-1;i++) a.cnt[i]-=mn;
    if(v>mn) for(int i=0;i<k-1;i++) if(!a.cnt[i])
    {a.val[i]=x; a.cnt[i]=v-mn; return;}
}
summary merge(summary a,summary b)
{
    for(int i=0;i<k-1;i++) if(b.cnt[i])
        ins(a,b.val[i],b.cnt[i]);
    return a;
}

例题1：Choosing Ads

看到区间查询占比大于某个阈值的数直接无脑上线段树维护 summary。
区间赋值直接清空 summary 然后插入一条 val=v,cnt=len 的记录即可。

这里要求的是出现频率 \geqslant p\%，不太熟悉，转化下题意：
题意等于出现频率 > (p-\epsilon)\% 等效于 k=\lceil{\dfrac{100}{p-\epsilon}}\rceil=\lfloor{\dfrac{100}p}\rfloor+1。然后我们发现 \text{k-heavy} 只需要维护 k-1=\lfloor{\dfrac{100}p} \rfloor 个数，恰好在题目要求的范围内，那把 summary 全部输出即可。

初始化 O(nk^2)，查询和修改均为 O(k^2 \log n)，总复杂度 O(nk^2 \log n)。

代码（半年前写的有点丑）

例题2：Destiny

也是线段树维护 summary，注意此题要求必须严格大于 \dfrac{r-l+1}k，所以不能像上一题一样把 summary 里的东西一股脑输出。写个区间求指定数字出现次数验证一下就行：

vector<int> pos[N];
void init() {for(int i=1;i<=n;i++) pos[a[i]].push_back(i);}
int count(int l,int r,int x)
{
    auto L=pos[x].begin(),R=pos[x].end();
    return upper_bound(L,R,r)-lower_bound(L,R,l);
}

代码（注意 \text{k-heavy} 的数一定也是 \text{k+1-heavy} 的，所以本题只需要维护 \text{5-heavy} 的 summary 而不是维护 \text{2-heavy} 到 \text{5-heavy} 的所有 summary）

后记：优化

猫树优化：
若不修改数组（如例 2）就可以用猫树来优化初始化和查询。
如果朴素猫树的话初始化复杂度为 O(nk^2 \log n)，查询复杂度 O(k^2)。
参考猫树维护线性基的做法不合并求值而是逐个插入可以把初始化复杂度降低至 O(nk \log n)。

插入优化：
朴素做法为 O(k) 插入 O(k^2) 合并，k 较大时有更优做法：
注意到 ins 函数内只有单点修改，求最小值，全局减这三个操作，那么可以用平衡树维护做到 O(\log k) 插入，即 O(k \log k) 合并。

ins 伪代码：

ins(a,x,v)
{
    p=a.findx(x)
    if(p.val!=-1) {a.set(p,{p.val,p.v+v}); return;}
    mn=a.findmin()
    if(mn.cnt==0) a.set(mn,{x,v})
    else if(mn.cnt<v)
        a.subtract(mn.cnt),a.set(mn,{x,v-mn.cnt});
    else a.subtract(v);
}

具体维护方式为维护两棵互相同步的平衡树，一棵以val为第一关键字以cnt为第二关键字，一棵以cnt为第一关键字val为第二关键字。
查询x对应的二元组在第一棵树上查，查cnt最小的二元组在第二棵树上查，拿到完整的二元组之后在另一个树上定位就是 trivial 的了。
至于全局减打一个全局减法标记就行了，记得返回 cnt 的时候减去标记和插入的时候加上标记即可。

把两个拼起来猫树优化+插入优化：
询问复杂度降低到 O(k \log k) 没啥说的，初始化倒有点意思：
由于猫树需要执行 O(n \log n) 次插入，所以只需要 O(n \log n \log k) 的时间就可以计算出所有所需的值，但是一一拷贝进前后缀数组里还是需要 O(nk \log n) 的时间。
考虑 summary 前/后缀和相邻两项的平衡树之间最多只有一个二元组不同，那么我们可以使用可持久化平衡树，这样只需要把根的编号和减法 tag 保存进前后缀数组里即可，这样预处理就只要 O(n \log n \log k) 的时间了，顺便也把空间复杂度降低到了 O(n \log n \log k)。

其实平时做题可能用上的也就猫树优化了毕竟出题人不太可能毒瘤到给你几千的 k 卡 O(k^2) 合并