★★★ 输入文件：nt2011_color.in 输出文件：nt2011_color.out 简单对比
时间限制：0.6 s 内存限制：512 MB
【试题来源】
2011中国国家集训队命题答辩
【问题描述】
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
【输入格式】
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
【输出格式】
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
【样例输入】
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
【样例输出】
4
4
3
4
4
3
4
【数据规模和约定】
对于40%数据，只包含第一类操作（无修改操作），且。 除此之外的20%的数据，N，M≤1000 对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。 时间限制：0.6s
在cogs上评测，暴力都可以过：
#include<cstdio> #include<cstring> using namespace std; bool f[1000005]; int a[10005],l,r,n,m,i,j,ans; char c; int main() { freopen("nt2011_color.in","r",stdin); freopen("nt2011_color.out","w",stdout); scanf("%d%d",&n,&m); for (i=1; i<=n; i++) scanf("%d",&a[i]); for (i=1; i<=m; i++) { c=' '; while (c!='Q'&&c!='R') c=getchar(); scanf("%d%d",&l,&r); if (c=='R') { a[l]=r; continue; } ans=0; memset(f,0,sizeof(f)); for (j=l; j<=r; j++) if (!f[a[j]]) ans++,f[a[j]]=true; printf("%d ",ans); } return 0; }
带修改莫队：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; struct hp{ int st,l,r,tim,num; }qst[100001]; int L,R,TIM,n,m,ans=0,a[100001],b[200002],c[100001]; int num[100001],change[100001][3],size,ansi[100001]; int cmp(const hp &a,const hp &b) { if ((a.st<b.st)||(a.st==b.st&&a.r<b.r)||(a.st==b.st&&b.r==a.r&&a.tim<b.tim)) return 1; else return 0; } void work(int i) { int l=qst[i].l,r=qst[i].r,tim=qst[i].tim; if (l!=r) { while (L<l) { if (num[a[L]]==1) ans--; num[a[L]]--; L++; } while (L>l) { L--; if (!num[a[L]]) ans++; num[a[L]]++; } while (R<r) { R++; if (!num[a[R]]) ans++; num[a[R]]++; } while (R>r) { if (num[a[R]]==1) ans--; num[a[R]]--; R--; } } while (tim>TIM) { TIM++; if (L<=change[TIM][0]&&change[TIM][0]<=R) { num[change[TIM][1]]--; if (num[change[TIM][1]]==0) ans--; num[change[TIM][2]]++; if (num[change[TIM][2]]==1) ans++; } a[change[TIM][0]]=change[TIM][2]; } while (tim<TIM) { if (L<=change[TIM][0]&&change[TIM][0]<=R) { num[change[TIM][2]]--; if (num[change[TIM][2]]==0) ans--; num[change[TIM][1]]++; if (num[change[TIM][1]]==1) ans++; } a[change[TIM][0]]=change[TIM][1]; TIM--; } if (qst[i].num) ansi[qst[i].num]=ans; } int main() { freopen("nt2011_color.in","r",stdin); freopen("nt2011_color.out","w",stdout); int i,per,numi=0,time=0; char opt; scanf("%d%d",&n,&m); per=sqrt(n); for (i=1;i<=n;++i) { scanf("%d",&a[i]); c[i]=b[i]=a[i]; } b[0]=n; for (i=1;i<=m;++i) { scanf("%c",&opt); while (opt!='Q'&&opt!='R') scanf("%c",&opt); if (opt=='Q') { scanf("%d%d",&qst[i].l,&qst[i].r); qst[i].st=qst[i].l/per+1; qst[i].num=++numi; qst[i].tim=time; } if (opt=='R') { time++; scanf("%d%d",&qst[i].l,&change[time][2]); qst[i].r=qst[i].l; qst[i].st=qst[i].l/per+1; qst[i].tim=time; qst[i].num=0; change[time][0]=qst[i].l; change[time][1]=c[qst[i].l]; c[qst[i].l]=change[time][2]; b[++b[0]]=change[time][2]; } } sort(b+1,b+b[0]+1); size=unique(b+1,b+b[0]+1)-b-1; for (i=1;i<=n;++i) a[i]=upper_bound(b+1,b+size+1,a[i])-b-1; for (i=1;i<=time;++i) { change[i][1]=upper_bound(b+1,b+size+1,change[i][1])-b-1; change[i][2]=upper_bound(b+1,b+size+1,change[i][2])-b-1; } sort(qst+1,qst+m+1,cmp); L=qst[1].l; R=qst[1].r; for (TIM=1;TIM<=qst[1].tim;++TIM) a[change[TIM][0]]=change[TIM][2]; for (i=qst[1].l;i<=qst[1].r;++i) { if (num[a[i]]==0) ans++; num[a[i]]++; } if (qst[1].num) ansi[qst[1].num]=ans; TIM=qst[1].tim; for (i=1;i<=m;++i) work(i); for (i=1;i<=numi;++i) printf("%d ",ansi[i]); }