数颜色

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

解题思路：

这是一道带修莫队的模板题，带修莫队支持单点修改，与原来基本的莫队算法相比：

首先要对询问的排序方式进行修改：

三个关键字：左侧端点，右侧多点，询问实践
1.如果左侧端点在同一块内，就按照左侧端点的块号由小到大排列
2.如果右侧端点在同一块内，就按照左侧端点的块号由小到大排列
3.如果不满足以上情况，就按照查询时间由小到大排列

修改代码：

判断被修改的下标是否在区间[l,r]内，如果在区间内，就从区间中删除原来的颜色，加上现在的颜色，并把当前下标对应的颜色改成要求的颜色。如果不在这个区间内就还原修改

void modify(int x,int t){
    if(nodes[t].index >= q[x].l && nodes[t].index <= q[x].r){
        del(a[nodes[t].index]);
        add(nodes[t].val);
    }
    swap(a[nodes[t].index],nodes[t].val);
}

记数的代码与普通莫队模板一致：

add：如果原数字不存在，ans++，cnt记数 + 1

del：如果原数组存在，ans–，cnt记数 - 1

void add(int x){
    if(cnt[x]++ == 0) ++ans;
}

void del(int x){
    if(--cnt[x] == 0) --ans;
}

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1000010;

int blo,n,m,qcnt,ccnt,ans,now,l = 2,r = 1;
int block[maxn],a[maxn],cnt[maxn],out[maxn];

struct query{
    int l,r,id,t;
}q[maxn];

struct node{
    int index,val;
}nodes[maxn];


void add(int x){
    if(cnt[x]++ == 0) ++ans;
}

void del(int x){
    if(--cnt[x] == 0) --ans;
}

void modify(int x,int t){
    if(nodes[t].index >= q[x].l && nodes[t].index <= q[x].r){
        del(a[nodes[t].index]);
        add(nodes[t].val);
    }
    swap(a[nodes[t].index],nodes[t].val);
}

bool cmp(query q1,query q2){
    if(block[q1.l] == block[q2.l]) return block[q1.l] < block[q2.l];
    else if(block[q1.r] == block[q2.r]) return block[q1.r] < block[q2.r];
    return q1.t < q2.t;
}


int main(){
    cin >> n >> m;
    blo = pow(n,2.0/3.0);
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
        block[i] = (i-1)/blo+1;
    }
    for(int i = 1 ; i <= m ; i++){
        string op;
        cin >> op;
        if(op[0] == 'Q'){
            ++qcnt;
            cin >> q[qcnt].l >> q[qcnt].r;
            q[qcnt].t = ccnt;
            q[qcnt].id = qcnt;
        }else{
            ++ccnt;
            cin >> nodes[ccnt].index >> nodes[ccnt].val;
        }
    }
    sort(q+1,q+qcnt+1,cmp);
    for(int i = 1 ; i <= qcnt ; i++){
        while(l > q[i].l) add(a[--l]);
        while(r < q[i].r) add(a[++r]);
        while(l < q[i].l) del(a[l++]);
        while(r > q[i].r) del(a[r--]);
        while(now < q[i].t) modify(i,++now);
        while(now > q[i].t) modify(i,now--);
        out[q[i].id] = ans;
    }
    for(int i = 1;  i <= qcnt ; i++){
        cout << out[i] << endl;
    }
    return 0;
}