撰写看到这个题，你不由自主地想到了莫队算法，（不了解莫队算法的看这里：莫队（一）：莫队初步基础与思想），但是你看到题目中还有修改操作，莫队GG了！怎么办？这时候就有了莫队的修改版：
带修莫队
前面说过，莫队算法是离线算法，不支持修改，强制在线需要另寻他法。的确，遇到强制在线的题目莫队基本上萎了，但是对于某些允许离线的带修改区间查询来说，莫队还是能用的。做法就是把莫队直接加上一维，变为带修莫队。
这里我们说的加上一维是什么意思呢？就是把修改操作进行编号，即加入了时间维度，编号即为“时间戳”。在进行查询的时候定义当前时间戳为\(t\)，对于每一个查询操作，如果当前的时间戳相对太大了，就说明这里包含了一些要查询的时间点之后的修改，就要把多改的改回去，反之则向后修改。只有当当前区间和查询区间完全一致时，查询结束，此时的答案即是这个查询的结果。
//区间完全一致当且仅当\(l,r,t\)三个维度的值完全一样
这就是带修莫队了，是不是很简单，于是我当年就写了个这：
别着急复制，这个只有40分，题面说： 本题可能轻微卡常数
那我得用尽所有优化方式了，小伙伴们可以把这一份40分代码拿去自己优化一下试试。AC代码放在下面了
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2*1e6+10;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
return x*f;
}
int N,M;
int a[MAXN],where[MAXN];
struct Query
{
int x,y,pre,id;
}Q[MAXN];
int Qnum=0;
struct Change
{
int pos,val;
}C[MAXN];
int Cnum=0;
int color[MAXN],ans=0,base,out[MAXN];
int comp(const Query &a,const Query &b){
if(a.x!=b.x) return where[a.x]<where[b.x];
if(a.y!=b.y) return where[a.y]<where[b.y];
return a.pre<b.pre;
}
void Add(int val){
if(++color[val]==1) ans++;
}
void Delet(int val){
if(--color[val]==0) ans--;
}
void Work(int now,int i){
if(C[now].pos>=Q[i].x&&C[now].pos<=Q[i].y){
if(--color[a[C[now].pos]]==0) ans--;
if(++color[C[now].val]==1) ans++;
}
swap(C[now].val,a[C[now].pos]);
}
void MoQueue(){
int l=1,r=0,now=0;
for(int i=1;i<=Qnum;i++) {
while(l<Q[i].x) Delet(a[l++]);
while(l>Q[i].x) Add(a[--l]);
while(r<Q[i].y) Add(a[++r]);
while(r>Q[i].y) Delet(a[r--]);
while(now<Q[i].pre) Work(++now,i);
while(now>Q[i].pre) Work(now--,i);
out[Q[i].id]=ans;
}
for(int i=1;i<=Qnum;i++)
printf("%d\n",out[i]);
}
int main(){
N=read();M=read();
base=sqrt(N);
for(int i=1;i<=N;i++) a[i]=read(),where[i]=(i-1)/base+1;
while(M--){
char opt[5];
scanf("%s",opt);
if(opt[0]=='Q'){
Q[++Qnum].x=read();
Q[Qnum].y=read();
Q[Qnum].pre=Cnum;
Q[Qnum].id=Qnum;
}
else if(opt[0]=='R'){
C[++Cnum].pos=read();
C[Cnum].val=read();
}
}
sort(Q+1,Q+Qnum+1,comp);
MoQueue();
return 0;
}
上面一份代码为什么凉凉？不光是少了几步优化，还有一点：有大佬证明了这道题分块大小设置为\(n^{\frac{2}{3}}\)时优于大小为\(\sqrt n\)的情况，总复杂度为\(O(n^{\frac{5}{3}})\)，优于大小为\(\sqrt n\)时最差\(O(n^2)\)的总复杂度。
所以就有了这样的代码！
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RE register
using namespace std;
const int N=1e6+10;
const int M=5e4+10;
int n,m,cntq,cntc;
int l=1,r,tim,now;
int be[M],a[M],ans[M];
int cnt[N];
struct query{
int l,r,id,time;
}q[M];
struct node{
int pos,col,last;
}c[M];
inline int Read(){
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
inline void Print(int x){
if(x>9)
Print(x/10);
putchar(x%10+'0');
}
inline bool CMP(query a,query b){
if(be[a.l]^be[b.l])
return be[a.l]<be[b.l];
else
if(be[a.r]^be[b.r])
return be[a.r]<be[b.r];
else return a.time<b.time;
}
//Ask和Change两部分看起来好像没必要拎出来
inline void Ask(int l,int r){
cntq++;
q[cntq].l=l;
q[cntq].r=r;
q[cntq].time=cntc;
q[cntq].id=cntq;
}
inline void Change(int p,int co){
cntc++;
c[cntc].pos=p;
c[cntc].col=co;
}
int main(){
n=Read();
m=Read();
int size=pow(n,2.0/3.0);
int bnum=ceil((double)n/size);
for(RE int i=1;i<=bnum;i++)
for(RE int j=(i-1)*size+1;j<=i*size;j++)
be[j]=i;
for(int i=1;i<=n;i++)
a[i]=Read();
for(RE int i=1;i<=m;i++){
char tmp;
scanf("\n%c",&tmp);
if(tmp=='Q'){
RE int l=Read(),r=Read();
Ask(l,r);
}
if(tmp=='R'){
RE int p=Read(),co=Read();
Change(p,co);
}
}
sort(q+1,q+cntq+1,CMP);
for(RE int i=1;i<=cntq;i++){
int ql=q[i].l,qr=q[i].r,qt=q[i].time;
while(l<ql) now-=!--cnt[a[l++]];
while(l>ql) now+=!cnt[a[--l]]++;
while(r<qr) now+=!cnt[a[++r]]++;
while(r>qr) now-=!--cnt[a[r--]];
//以下就是带修莫队的时间点左右横跳实现部分
while(tim<qt){
tim++;
if(ql<=c[tim].pos&&c[tim].pos<=qr)
now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].col]++;
swap(a[c[tim].pos],c[tim].col);//记录上一次修改的操作，一点小小的优化
}
while(tim>qt){
if(ql<=c[tim].pos&&c[tim].pos<=qr)
now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].col]++;
swap(a[c[tim].pos],c[tim].col);
tim--;
}
ans[q[i].id]=now;
}
for(RE int i=1;i<=cntq;i++){
Print(ans[i]);
putchar('\n');
}
return 0;
}
想必你已经学会了带修莫队，如果你还没有了解过其他莫队算法看这里：
莫队（三）：莫队算法的拓展