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。


带修改莫队膜版

没写过莫队就写带修改心中慌张

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std; struct ask{
int L,R,id,tm;
}; struct req{
int ps,cl,pre;
}; const int maxn=,maxnum=,maxm=,maxr=; int CL=,CR=,ans=,tim,n,m,k,cnt=,sz=;
int color[maxn],num[maxnum];
int las[maxn],answer[maxm];
bool vis[maxn];
ask e[maxm];
req w[maxr]; inline bool cmp(const ask &n1,const ask &n2){
return (n1.L/tim)==(n2.L/tim)?n1.R<n2.R:n1.L<n2.L;
} void cala(int x){
if(vis[x]){
if((--num[color[x]])==) --ans;
}
else{
if((++num[color[x]])==) ++ans;
}
vis[x]=!vis[x];
} void change(int x,int c){
if(vis[x]){ cala(x); color[x]=c; cala(x); }
else color[x]=c;
} int main(){
//freopen("temp.in","r",stdin);
char opt[];
int x,y;
scanf("%d%d",&n,&m);
tim=sqrt(n); for(int i=;i<=n;i++){
scanf("%d",&color[i]);
las[i]=color[i];
} for(int i=;i<m;i++){
scanf("%s%d%d",opt,&x,&y);
if(opt[]=='R'){
w[++cnt].ps=x;
w[cnt].cl=y;
w[cnt].pre=las[x];
las[x]=y;
}
else{
e[++sz].L=x;
e[sz].R=y;
e[sz].id=sz;
e[sz].tm=cnt;
}
} sort(e+,e++sz,cmp); for(int i=;i<=sz;i++){
for(int j=e[i-].tm+;j<=e[i].tm;j++)
change(w[j].ps,w[j].cl);
for(int j=e[i-].tm;j>=e[i].tm+;j--)
change(w[j].ps,w[j].pre); int l=e[i].L,r=e[i].R;
while(CL<l) cala(CL++);
while(CL>l) cala(--CL);
while(CR<r) cala(++CR);
while(CR>r) cala(CR--); answer[e[i].id]=ans;
} for(int i=;i<=sz;i++)
printf("%d\n",answer[i]);
return ;
}

上一篇:【HDOJ】【3530】Subsequence


下一篇:06 . Nginx静态资源缓存