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。


Solution

带修莫队裸题。

Code

/*Program from Luvwgyx*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
const int maxm=1e6+10;
struct Query2{int p,c;}q2[maxn];
struct Query1{int l,r,t,pos;}q1[maxn];
int n,m,B,tot1,tot2,ret,a[maxn],cnt[maxm],ans[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
bool cmp(Query1 x,Query1 y){return x.l/B==y.l/B?(x.r/B==y.r/B?x.t<y.t:x.r/B<y.r/B):x.l/B<y.l/B;}
void add(int x){if(!cnt[x])ret++;cnt[x]++;}
void del(int x){cnt[x]--;if(!cnt[x])ret--;}
void change(int x,int tim){
    if(q1[x].l<=q2[tim].p&&q2[tim].p<=q1[x].r)del(a[q2[tim].p]),add(q2[tim].c);
    swap(a[q2[tim].p],q2[tim].c);
}
int main(){
    n=read();m=read();B=pow(n,0.66666666);
    for(int i=1;i<=n;i++)a[i]=read();char opt[10];
    for(int i=1;i<=m;i++){
        scanf("%s",opt);
        if(opt[0]=='Q')q1[++tot1]=(Query1){read(),read(),tot2,tot1};
        else q2[++tot2]=(Query2){read(),read()};
    }sort(q1+1,q1+tot1+1,cmp);int l=1,r=0,now=0;
    for(int i=1;i<=m;i++){
        while(l>q1[i].l)add(a[--l]);
        while(r<q1[i].r)add(a[++r]);
        while(l<q1[i].l)del(a[l++]);
        while(r>q1[i].r)del(a[r--]);
        while(now<q1[i].t)change(i,++now);
        while(now>q1[i].t)change(i,now--);
        ans[q1[i].pos]=ret;
    }for(int i=1;i<=tot1;i++)write(ans[i]);
    return 0;
}

发表评论