普通莫队是不带修改的，而如果要支持修改操作就要使用待修莫队了。
先来看到模板题，这道题就是要求区间不同数的个数，并支持修改操作。
如果没有修改操作，这道题就是普通莫队的一道模板题。
考虑加入修改操作，每次进行修改时，都会对一些询问产生影响。
对每次询问加入一个维度——之前有多少次修改操作，和 \(l,r\) 相类似，每次也可以通过加入或撤销来移动。
块的大小要开 \(n^{2/3}\)，时间复杂度大概是 \(O(n^{5/3})\) 这个级别的（懒得证了）。
具体还是看代码吧：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=133340,M=1e6+10;
int n,m,S,a[N],qnum=0,cnum=0;
struct Query{
int l,r,stp,id; //stp为询问之前有多少次修改操作
bool operator<(Query x){ //排序
if(l/S!=x.l/S)return l<x.l;
if(r/S!=x.r/S)return r<x.r;
return stp<x.stp;
}
}q[N];
struct Change{ //修改操作
int pos,val;
}c[N];
int cnt[M],ans[N],res=0;
void add(int x){
if(!cnt[a[x]])res++;
cnt[a[x]]++;
}
void del(int x){
cnt[a[x]]--;
if(!cnt[a[x]])res--;
}
void move(int x,int i){ //移动stp这一维
if(c[x].pos>=q[i].l&&c[x].pos<=q[i].r){ //只有在区间范围之内才修改答案
cnt[a[c[x].pos]]--;
if(!cnt[a[c[x].pos]])res--;
if(!cnt[c[x].val])res++;
cnt[c[x].val]++;
}
swap(c[x].val,a[c[x].pos]); //直接交换，下次再改就能改回来
}
int main(){
scanf("%d%d",&n,&m);
S=cbrt(n),S*=S;
for(int i=1;i<=n;i++)scanf("%d",a+i);
char op[2];
for(int i=1;i<=m;i++){
scanf("%s",op);
if(op[0]=='Q'){
++qnum;
scanf("%d%d",&q[qnum].l,&q[qnum].r);
q[qnum].stp=cnum,q[qnum].id=qnum;
}
else{
++cnum;
scanf("%d%d",&c[cnum].pos,&c[cnum].val);
}
}
sort(q+1,q+1+qnum);
int l=1,r=0,stp=0;
for(int i=1;i<=qnum;i++){
while(r<q[i].r)add(++r);
while(l>q[i].l)add(--l);
while(l<q[i].l)del(l++);
while(r>q[i].r)del(r--);
while(stp<q[i].stp)move(++stp,i);
while(stp>q[i].stp)move(stp--,i);
ans[q[i].id]=res;
}
for(int i=1;i<=qnum;i++)printf("%d\n",ans[i]);
return 0;
}
参考资料：《待修莫队算法》——自为风月马前卒