数列分块入门 #9 莫队做法
w33z8kqrqk8zzzx33
·
·
个人记录
话说有人先做 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