带修改莫队
请确保您已经会普通莫队算法了。如果您还不会,请先阅读前面的 普通莫队算法。
特点
普通莫队是不能带修改的。
我们可以强行让它可以修改,就像 DP 一样,可以强行加上一维 时间维, 表示这次操作的时间。
时间维表示经历的修改次数。
即把询问
那么我们的坐标也可以在时间维上移动,即
这样的转移也是
可以用和普通莫队类似的方法排序转移,做到
这一次我们排序的方式是以
最优块长以及时间复杂度分析
我们设序列长为
带修莫队排序的第二关键字是右端点所在块编号,不同于普通莫队。
想一想,如果不把右端点分块:
- 乱序的右端点对于每个询问会移动
次。 - 有序的右端点会带来乱序的时间,每次询问会移动
次。
无论哪一种情况,带来的时间开销都无法接受。
接下来分析时间复杂度。
设块长为
每「组」左右端点不换块的询问
左右端点换块的时间忽略不计。
表示一下就是:
考虑求导求此式极小值。设
得
也就是当块长取
常说的
实际操作中还是推荐设定
例题
我们不难发现,如果不带操作 1(修改)的话,我们就能轻松用普通莫队解决。
但是题目还带单点修改,所以用 带修改的莫队。
过程
先考虑普通莫队的做法:
- 每次扩大区间时,每加入一个数字,则统计它已经出现的次数,如果加入前这种数字出现次数为
,则说明这是一种新的数字,答案 。然后这种数字的出现次数 。 - 每次减小区间时,每删除一个数字,则统计它删除后的出现次数,如果删除后这种数字出现次数为
,则说明这种数字已经从当前的区间内删光了,也就是当前区间减少了一种颜色,答案 。然后这种数字的出现次数 。
现在再来考虑修改:
- 单点修改,把某一位的数字修改掉。假如我们是从一个经历修改次数为
的询问转移到一个经历修改次数为 的询问上,且 的话,我们就需要把第 个到第 个修改强行加上。 - 假如
的话,则需要把第 个到第 个修改强行还原。
怎么强行加上一个修改呢?假设一个修改是修改第
- 加上这个修改:我们首先判断
是否在区间 内。如果是的话,我们等于是从区间中删掉颜色 ,加上颜色 ,并且当前颜色序列的第 项的颜色改成 。如果不在区间 内的话,我们就直接修改当前颜色序列的第 项为 。 - 还原这个修改:等于加上一个修改第
项、把颜色 改成颜色 的修改。
因此这道题就这样用带修改莫队轻松解决啦!
实现
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
|
本页面最近更新:2023/7/30 10:47:50,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:countercurrent-time, Ir1d, renbaoshuo, 2008verser, 383494, Backl1ght, CCXXXI, Chrogeek, Enter-tainer, greyqz, Henry-ZHR, iamtwz, kenlig, MicDZ, O-Omega, ouuan, StudyingFather, Tiphereth-A, yzxoi
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用