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
Q
Q
R
Q
Q
Sample Output
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
2016.3.2新加数据两组by Nano_Ape
Solution
先上简单的暴力，可以水过
#include <stdio.h>
#include <string.h>
#define M 1000010 inline int Rin() {
int x=,c=getchar(),f=;
for(; c<||c>; c=getchar())
if(c==)f=-;
for(; c>&&c<; c=getchar())
x=(x<<)+(x<<)+c-;
return x*f; } char c;
int g[M],n,m,a[M],top,x,y,i,mark[M],ans; int main() {
n=Rin(),m=Rin();
for(i=; i<=n; i++) {
a[i]=Rin();
if(!g[a[i]])
g[a[i]]=++top;
a[i]=g[a[i]]; }
while(m--) {
do c=getchar(); while(c!='Q'&&c!='R');
x=Rin(),y=Rin();
if(c=='Q') {
for(i=x,ans=; i<=y; i++)
if(mark[a[i]]!=m)
mark[a[i]]=m,ans++;
printf("%d\n",ans);
}
else {
if(!g[y])g[y]=++top;
a[x]=g[y];
}
}
return ;
}
一下是莫队的做法
otz menci
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 10010
#define M 1000010
#define RG register
#define inline __inline__ __attribute__((always_inline)) inline void Rin(RG int &x) {
x=;RG int c=getchar(),f=;
for(; c<||c>; c=getchar())
if(c==)f=-;
for(; c>&&c<; c=getchar())
x=(x<<)+(x<<)+c-;
x*=f; } int n,m,block_size,a[N],utop,qtop,ans[N],cnt[M]; struct Update {
int pos,eld,now; }U[N]; struct Request{
int tim,l,r,id; bool operator < (const Request &other)const {
if(l/block_size == other.l/block_size) {
if(r/block_size == other.r/block_size)
return tim < other.tim;
return r/block_size < other.r/block_size; }
return l/block_size < other.l/block_size; } }Q[N]; inline void prepare() {
static int nowlist[N];
memcpy(nowlist,a,sizeof a);
for(RG int i=; i<=utop; i++) {
U[i].eld=nowlist[U[i].pos];
nowlist[U[i].pos]=U[i].now; } } inline void extend(RG int &tmp,RG int pos,RG int dir) {
if(dir == ) {
if(++cnt[a[pos]]==)
tmp++; }
else
if(--cnt[a[pos]]==)
tmp--; } inline void modify(RG int &tmp,RG int T,RG int l,RG int r,RG int dir) {
RG Update x=U[T];
if(dir == ) {
a[x.pos]=x.now;
if(x.pos >=l && x.pos <= r) {
if(--cnt[x.eld]==)tmp--;
if(++cnt[x.now]==)tmp++; } }
else {
if(x.pos >=l && x.pos <= r) {
if(--cnt[x.now]==)tmp--;
if(++cnt[x.eld]==)tmp++; }
a[x.pos]=x.eld; } } inline void block_solve() {
for(RG int l=,r=,ans=,T=,i=; i<=qtop; i++) {
while(r < Q[i].r)extend(ans,++r,);
while(r > Q[i].r)extend(ans,r--,-); while(l > Q[i].l)extend(ans,--l,);
while(l < Q[i].l)extend(ans,l++,-); while(T < Q[i].tim)modify(ans,++T,l,r,);
while(T > Q[i].tim)modify(ans,T--,l,r,-);
:: ans[Q[i].id]=ans; } } int main() { Rin(n),Rin(m);
for(RG int i=; i<=n; i++)
Rin(a[i]);
for(RG int i=; i<=m; i++) {
RG char c;
do c=getchar(); while(c != 'Q'&&c != 'R');
if(c == 'Q') {
++qtop;
Rin(Q[qtop].l),Rin(Q[qtop].r);
Q[qtop].id=qtop;
Q[qtop].tim=utop; }
else {
++utop;
Rin(U[utop].pos),Rin(U[utop].now); } } prepare();
block_size=floor(pow(n,2.0/)+);
std::sort(Q+,Q++qtop);
block_solve(); for(RG int i=; i<=qtop;i++)
printf("%d\n",ans[i]);
return ; }