https://www.lydsy.com/JudgeOnline/problem.php?id=2120
标题里是两种不同的解法。
带修改的莫队和普通莫队比多了个修改操作,影响不大,但是注意一下细节不要出现zz错误。
这道题修改的数量比较少可以写莫队,但是如果修改数量多或者是特别极限的数据大概是不行的吧。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
const int maxn=;
using namespace std;
int n,m;
char ch[]={};
int clo[maxn]={},las[maxn]={};
struct node{
int pos,clo,pre;
}t[maxn];int tr=;
struct nod{
int l,r,id,pre;
}q[maxn];int tq=;
int b[maxn]={},ans[maxn]={},ans1=;
int vis[maxn*]={};
bool mcmp(nod aa,nod bb){
return (b[aa.l]==b[bb.l])?((aa.r==bb.r)?aa.id<bb.id:aa.r<bb.r):(b[aa.l]<b[bb.l]);
}
void doit(int x,int v){
if(v){
if(!vis[clo[x]])ans1++;
vis[clo[x]]++;
}
else{
if(vis[clo[x]]==)ans1--;
vis[clo[x]]--;
}
}
void change(int x,int y,int v){
//cout<<x<<y<<clo[x]<<v<<endl;
if(v){
doit(x,);
clo[x]=y;
doit(x,);
}clo[x]=y;
}
void work(){
int l=,r=,now=;
for(int i=;i<=tq;i++){
while(now<q[i].pre){now++;change(t[now].pos,t[now].clo,l<=t[now].pos&&t[now].pos<=r);}
while(now>q[i].pre){change(t[now].pos,t[now].pre,l<=t[now].pos&&t[now].pos<=r);now--;}
while(r<q[i].r)doit(++r,);
while(l>q[i].l)doit(--l,);
while(r>q[i].r){doit(r,);--r;}
while(l<q[i].l){doit(l,);++l;}
ans[q[i].id]=ans1;
}
for(int i=;i<=tq;i++){
printf("%d\n",ans[i]);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){scanf("%d",&clo[i]);las[i]=clo[i];}
int x,y;
for(int i=;i<=m;i++){
scanf("%s",ch);scanf("%d%d",&x,&y);
if(ch[]=='Q'){ q[++tq].l=x; q[tq].r=y; q[tq].id=tq; q[tq].pre=tr; }
else{ t[++tr].pos=x; t[tr].clo=y;t[tr].pre=las[x];las[x]=y;}
}int siz=(int)sqrt((double)n);
for(int i=;i<=n;i++)b[i]=(i-)/siz+;
sort(q+,q++tq,mcmp);
work();
return ;
}