数列分块入门 #9 莫队做法

~~话说有人先做 Ynoi 后做数列分块入门么~~ 假如仅仅需要计算众数出现次数，怎么做？可以用莫队维护当前区间 cnt 数组和 cntcnt 数组，其中 $cnt[i]$ 等于当前区间 $i$ 出现了多少次，$cntcnt[i]$ 等于当前区间有多少值出现了恰好 $i$ 次。同时维护一个 $modecnt$ 等于当前区间众数出现次数，这样： - 添加一个元素的时候只可能让 $modecnt$ 增加，更具体 $modecnt$ 会变为 $\max(modecnt,cnt[i])$ - 删除一个元素 $modecnt$ 最多减少 1，会减少 1 当且仅当修改后 $cntcnt[modecnt]=0$ 莫队添加删除即可。考虑如何扩展到计算最小众数。我们对每一个出现次数做一次值域分块，其中 $zyfk[i][j]$ 等于“有多少个值在值块 $j$ 内，出现了恰好 $i$次”。这个一个添加删除仅仅会修改 $O(1)$ 值，可以莫队顺便维护。这个数组会占用 $O(n\sqrt n)$ 空间。 来计算答案，就看 $zyfk[modecnt][???]$ 这数组了。先遍历所有 $???$ 得到第一个非零的值块，这值块必定包含最小出现 $modecnt$ 次的值，或者最小众数。找到这个块再遍历块里所有值，查询一下 $cnt[i]$，如果等于 $modecnt$ 直接输出。 跑的飞快，根本不需要卡常，仅仅被回滚莫队吊打。 实战：[https://loj.ac/s/1016775](https://loj.ac/s/1016775)