给定长度为n的序列, 要求支持: 1. 单点修改. 2. 查询某区间的众数, 如有多个, 取最小者 / 查询某区间众数的出现次数.
本文主要是cls <区间众数解题报告> 的学习笔记.
代码实现: [bzoj 2724] [Violet 6] 蒲公英 强制在线, 无修改的区间众数.
引理
记可重集的众数为. 否则, 只在中出现, 由于, 不是众数. 之所以关注这个引理, 是因为区间众数不具备最优子结构, 但往可重集中加入一个新数, 众数的变化是可控的.
朴素算法
- 离散化.
- 扫描查询的区间, 统计每种数的出现次数.
- 扫描查询的区间, 找出众数.
- 扫描查询的区间, 将计数器清零.
每次询问时间.
不带修改
离线
莫队算法. 用数据结构地转移.
在线
分成块. 预处理表示块i到块j的众数. 设待查询的区间为, 是一些整块, 和的长度均不超过. 已经预处理出来了, 只用将其和, 中的数作比较. 现在的问题是怎样求一个数在区间中的出现次数. ### 算法一 可持久化线段树. 每查一次. ### 算法二 对每种数开一个vector, 记录它在整个序列中出现的位置, 二分查找. . ### 算法三 考虑求在中的出现次数. 为了地回答, 需要预处理一些信息. - : 0~i块中x的出现次数. 的时空开销. - : 位置i所在块的开头~位置i中x的出现次数. 第一次在某块中遇到某数时给它分配一个id, 将作为计数器. 的时空开销. 这样, 就可以拆成两部分了.
预处理的方法和查询类似. 边扫描边统计每种数的出现次数, 比较与块中各数的出现次数, 更新. 采用算法一, 二, 时间复杂度, 空间复杂度. 采用算法三, 时间复杂度, 空间复杂度.
带修改
先只考虑回答区间众数出现次数. 基本思路是在不带修改的算法上进行扩充.
先看数组. 设把序列分为块, 那么, 一次修改将影响对块的值. 现在不能取为, 最后来计算合适的值. 对每一对块, 记录每种数的出现次数, 最大出现次数, 出现次的数有多少种. 修改将使得一种数出现次数-1, 一种数出现次数+1, 均使最大出现次数至多变化1, 所以能用的时间修改.
再看. 依旧分块, - 块0~i中x的出现次数至多有个需要修改. - 位置i所在块开头~位置i的范围内x的出现次数也至多有个需要修改.
于是, 并不影响总的时间复杂度.
预处理时间 (将的信息复制到需要), 修改, 查询, 空间, 取, 总的时间复杂度, 空间复杂度.
我的脑补: 如果还要回答众数的值, 可以用set维护每对块中出现次的数是哪些, 不过时间复杂度好像有点高, 只是理论上优于朴素算法......