题解 P1903 【【模板】分块/带修改莫队（数颜色）】
分块解法
（这里参考的是黄学长的做法，详见 http://hzwer.com/2793.html）
如果不考虑修改操作，我们可以用类似区间众数的方法求解，但加入修改就显得麻烦了。
我们可以考虑记录两个数组 lst[],pr[]：
· pr[i] 表示前一个和 i 相同颜色的画笔的所在位置
· lst[i] 表示颜色为 i 的画笔之前最后出现的位置，用于更新pr[i]
那么，询问 [l, r]：
· 对于不完整的块，暴力判断：当 pr[i] < l 时，则当前区间没有画笔和 i 颜色相同，我们将记录的答案++
（黄学长的博客中 pr[i] < r 应该属于笔误）
· 对于完整的块，我们用类似 教主的魔法 的做法，将 pr[i] 存入另一个数组排序，然后以 l 为界二分，则区间分界左边都满足 pr[i] < l，计入答案即可
但还有一个问题，修改操作似乎只能暴力重构了，但我们注意到题目中 修改操作不多于1000次 且 N≤10000，M≤10000，因此暴力可以卡过。（不过我这里的写法和黄学长不太一样，黄学长是一旦发现 pr[] 值改变就重新对所在块排序，但我是将这些改变情况合并到一个个块内处理，个人认为要快些）
最后附上代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int Maxn = 0x3f3f3f3f;
const int N = 1e4 + 5, M = 105;
int bl[M], br[M], a[N], tr[N], pr[N], lst[N * M];
int n, m, s, S, Q;
inline int get()
{
char ch; bool f = false; int res = 0;
while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
if (ch == '-') f = true;
else res = ch - '0';
while ((ch = getchar()) >='0' && ch <= '9')
res = (res << 3) + (res << 1) + ch - '0';
return f? ~res + 1 : res;
}
inline void put(int x)
{
if (x < 0)
x = ~x + 1, putchar('-');
if (x > 9) put(x / 10);
putchar(x % 10 + 48);
}
inline void Flag(const int x)
{
int L = bl[x], R = br[x];
for (int i = L; i <= R; ++i) tr[i] = pr[i];
sort(tr + L, tr + R + 1);
}
inline int Find(const int x, const int vi)
{
int l = bl[x], r = br[x];
while (l <= r)
{
int mid = l + r >> 1;
if (tr[mid] < vi) l = mid + 1;
else r = mid - 1;
}
return l - bl[x];
}
inline void Und(const int x, const int vi)
{
for (int i = 1; i <= n; ++i) lst[a[i]] = 0;
a[x] = vi; bool f; int cur;
for (int i = 1; i <= s; ++i)
{
f = false;
for (int j = bl[i]; j <= br[i]; ++j)
{
cur = pr[j];
pr[j] = lst[a[j]];
if (pr[j] != cur) f = true;
lst[a[j]] = j;
}
if (f) Flag(i);
}
}
inline int Que(const int l, const int r)
{
int L = (l - 1) / S + 1, R = (r - 1) / S + 1, num = 0;
if (r - l < (S << 1))
{
for (int i = l; i <= r; ++i) if (pr[i] < l) num++;
return num;
}
if (l == bl[L]) L--; if (r == br[R]) R++;
int ed = br[L], st = bl[R];
for (int i = l; i <= ed; ++i) if (pr[i] < l) num++;
for (int i = st; i <= r; ++i) if (pr[i] < l) num++;
for (int i = L + 1; i < R; ++i) num += Find(i, l);
return num;
}
int main()
{
n = get(); Q = get(); S = sqrt(n);
int x, y; char tp;
for (int i = 1; i <= n; ++i) a[i] = get();
for (int i = 1; i <= n; ++i)
if (i % S == 1) br[s] = i - 1, bl[++s] = i;
br[s] = n; bl[s + 1] = br[s + 1] = n + 1;
for (int i = 1; i <= n; ++i)
pr[i] = lst[a[i]], lst[a[i]] = i;
for (int i = 1; i <= s; ++i) Flag(i);
while (Q--)
{
while ((tp = getchar()) != 'Q' && tp != 'R');
x = get(); y = get();
if (tp == 'Q') put(Que(x, y)), putchar('\n');
else Und(x, y);
}
return 0;
}