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。


2016.3.2新加数据两组by Nano_Ape


解法：带修改的莫对算法，http://blog.csdn.net/doyouseeman/article/details/51869932 在这里学习了一下，带修改的莫队只支持单点修改，区间查询的情况，在进行转移的时候不仅需要维护区间，更需要去维护时间。

就是对于当前询问，在这之前的没有修改的修改操作要进行修改，而这之后的已经修改的修改操作要恢复回去。


 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, m;
struct node{
    int pos,color,pre;
}w[maxn];
struct node2{
    int l,r,id,time;
}q[maxn];
int belong[maxn], last[maxn], color[maxn], cnt, sz, vis[maxn], num[1000002], ans[maxn], Ans;
bool cmp(node2 a, node2 b){
    if(belong[a.l]==belong[b.l]) return a.r<b.r;
    return belong[a.l]<belong[b.l];
}
void calc(int x){
    if(vis[x]){
        if(!--num[color[x]]) Ans--;
    }else{
        if(++num[color[x]]==1) Ans++;
    }
    vis[x]^=1;
}
void change(int x, int c){
    if(vis[x]){
        calc(x);
        color[x]=c;
        calc(x);
    }else{
        color[x]=c;
    }
}

int main(){
    scanf("%d %d", &n,&m);
    for(int i=1; i<=n; i++) scanf("%d", &color[i]), last[i]=color[i];
    for(int i=1; i<=m; i++){
        char s[10];
        scanf("%s", s);
        int x, y;
        scanf("%d %d", &x,&y);
        if(s[0]=='R'){
            w[++cnt].pos=x,w[cnt].color=y,w[cnt].pre=last[x];//记录更改之前的颜色
            last[x]=y;
        }else{
            q[++sz].l=x,q[sz].r=y,q[sz].id=sz,q[sz].time=cnt;
        }
    }
    int block=250;
    for(int i=1; i<=n; i++) belong[i]=(i-1)/block+1;
    sort(q+1,q+sz+1,cmp);
    int l,r;
    l=1,r=0;
    for(int i=1; i<=sz; i++){
        for(int j=q[i-1].time+1;j<=q[i].time;j++) change(w[j].pos,w[j].color);
        for(int j=q[i-1].time;j>q[i].time;j--) change(w[j].pos,w[j].pre);
        while(l<q[i].l) calc(l++);
        while(l>q[i].l) calc(--l);
        while(r<q[i].r) calc(++r);
        while(r>q[i].r) calc(r--);
        ans[q[i].id] = Ans;
    }
    for(int i=1; i<=sz; i++) printf("%d\n", ans[i]);
}