[文章目录]
Description
小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。
修改次数1000次，n<=10000 m<=10000
修改次数少，直接莫队记录修改时间戳即可。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[10010],blo;
int num[1001000],fna[10100];
int cnt,tot;
struct ques
{
int l,r,p,id;
}q[10010];
struct fix
{
int p,u,n;
}f[1100];
inline bool cmp(ques x,ques y) {return x.l/blo==y.l/blo?x.r<y.r:x.l<y.l;}
int l=1,r,tim,ans;
inline void add(int val) {ans+=(!num[val]); num[val]++;}
inline void del(int val) {num[val]--; ans-=(!num[val]);}
int main()
{
scanf("%d%d",&n,&m); blo=sqrt(1.0*n);
for(int i=1;i<=n;++i) scanf("%d",w+i);
char sw[10];
while(m--)
{
scanf("%s",sw);
if(sw[0]=='Q')
{
cnt++; scanf("%d%d",&q[cnt].l,&q[cnt].r);
q[cnt].p=tot; q[cnt].id=cnt;
}
else
{
tot++; scanf("%d%d",&f[tot].p,&f[tot].n);
f[tot].u=w[f[tot].p]; w[f[tot].p]=f[tot].n;
}
}
sort(q+1,q+cnt+1,cmp); tim=tot;
for(int i=1;i<=cnt;++i)
{
while(tim<q[i].p)
{
tim++; w[f[tim].p]=f[tim].n;
if(f[tim].p>=l&&f[tim].p<=r) del(f[tim].u),add(f[tim].n);
}
while(tim>q[i].p)
{
w[f[tim].p]=f[tim].u;
if(f[tim].p>=l&&f[tim].p<=r) del(f[tim].n),add(f[tim].u);
tim--;
}
while(r<q[i].r) add(w[++r]);
while(l>q[i].l) add(w[--l]);
while(r>q[i].r) del(w[r--]);
while(l<q[i].l) del(w[l++]);
fna[q[i].id]=ans;
}
for(int i=1;i<=cnt;++i) printf("%d\n",fna[i]);
return 0;
}