BZOJ2120&2453 数颜色 带修改莫队

发布于 2017-09-23  4.46k 次阅读


[toggle hide="yes" title="题目" color=""]

Description
墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?

Input
第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。

Output
对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

Sample Input
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

Sample Output
4
4
3
4

HINT
对于100%的数据,N≤10000,M≤10000,修改操作不多于1000次,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

[/toggle]

带修改的莫队,在普通莫队的基础上增加了在时间轴上的滚动,将询问和修改分别记录,保存每个询问的左右端点,以及在当前询问之前进行了多少次修改,将块长设置为n^(2/3),保证理论时间复杂度是O(n^(5/3)),再将询问按照(左端点所在块,右端点所在块,时间),进行三元组排序,可以感性理解一下查询区间移动的趋势,就能知道这样做的优势了,比较严谨的推导在这里:https://blog.sengxian.com/algorithms/mo-s-algorithm

对于这道题,我的做法是先将莫队的初始区间拉到(1,n),也就是序列的初始状态,预处理每个修改操作修改前的值,方便以后撤销修改,之后再进行莫队的操作,比较水(个人不是非常喜欢把修改操作全写成函数,感觉边界处理不如分别搞直观易调试)。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974