[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)，也就是序列的初始状态，预处理每个修改操作修改前的值，方便以后撤销修改，之后再进行莫队的操作，比较水（个人不是非常喜欢把修改操作全写成函数，感觉边界处理不如分别搞直观易调试）。