BZOJ2120 数颜色
Description
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
Input
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。
Output
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔*有几种不同颜色的画笔。
Sample Input
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
Sample Output
4
4
3
4
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
挺好的一道带修改莫队入门题
一开始没有考虑在修改的基础上进行累加，不能一直从原状态上进行累加，因为时间是固定的，所以我们可以保证修改一定是有序的
就是代码中的last数组
其他没什么好说的，但是提醒一下，虽然sqrt（n）也可以过，但是siz取n的三分之二次方最优
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
struct Node{int pos,x,y;}t[N];
struct Ask{int l,r,id,tim;}p[N];
int block[N],a[N],last[N],ans[N],cnt[N];
int n,m,totp=0,tott=0;
int l=1,r=0,tmp=0,ansnow=0;
bool cmp1(Ask a,Ask b){
if(block[a.l]==block[b.l])return a.r<b.r;
else return block[a.l]<block[b.l];
}
void modify(int pos,int y){
if(l<=pos&&pos<=r){
if(--cnt[a[pos]]==0)ansnow--;
a[pos]=y;
if(++cnt[a[pos]]==1)ansnow++;
}else a[pos]=y;
}
void update(int pos,int typ){
if(typ==1)ansnow+=(++cnt[a[pos]]==1);
else ansnow-=(--cnt[a[pos]]==0);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),last[i]=a[i];
for(int i=1;i<=m;i++){
char c[5];int x,y;
scanf("%s%d%d",c,&x,&y);
if(c[0]=='Q')p[++totp]=(Ask){x,y,totp,tott};
else{
t[++tott]=(Node){x,last[x],y};
last[x]=y;
}
}
int siz=sqrt(n);
for(int i=1;i<=n;i++)block[i]=(i-1)/siz+1;
sort(p+1,p+totp+1,cmp1);
for(int i=1;i<=totp;i++){
while(tmp<p[i].tim)++tmp,modify(t[tmp].pos,t[tmp].y);
while(tmp>p[i].tim)modify(t[tmp].pos,t[tmp].x),tmp--;
while(l<p[i].l)update(l++,-1);
while(l>p[i].l)update(--l,1);
while(r<p[i].r)update(++r,1);
while(r>p[i].r)update(r--,-1);
ans[p[i].id]=ansnow;
}
for(int i=1;i<=totp;i++)printf("%d\n",ans[i]);
return 0;
}