题目链接

2521. 数颜色

墨墨购买了一套 \(N\) 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。

墨墨会像你发布如下指令：

1. Q L R 代表询问你从第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。
2. R P Col 把第 \(P\) 支画笔替换为颜色 \(Col\)。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入格式

第 \(1\) 行两个整数 \(N,M\)，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第 \(2\) 行 \(N\) 个整数，分别代表初始画笔排中第 \(i\) 支画笔的颜色。

第 \(3\) 行到第 \(2+M\) 行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式

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

数据范围

\(1 \le N,M \le 10000\),
修改操作不多于 \(1000\) 次，
所有的输入数据中出现的所有整数均大于等于 \(1\) 且不超过 \(10^6\)。

输入样例：

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

输出样例：

4
4
3
4

解题思路

带修改的莫队

莫队算法是暴力离线算法，一般不支持修改操作，如果需要修改操作，则需要在原基础上增加一个维度，即 \((l,r,t)\)，将区间分块，设其长度为 \(len\)，则每一个时间戳有 \(n/len\) 块长度为 \(len\) 的块，同理每次先将 \(l,r\) 两个指针移到询问端点上，再将 \(t\) 指针暴力移到对应时间戳即可
复杂度分析：分别考虑三个指针的总时间复杂度，\(l\) 指针分为块内和块间的复杂度，块内复杂度为 \(O(m\times len)\)，块间复杂度为 \(O(2len\times n/len)\)，故其复杂度为 \(O(m\times len+n)\approx O(m\times len)\)，\(r\) 指针也同样考虑，块内复杂度为 \(O(m\times len)\)，

• 时间复杂度：\(O()\)

代码