题目描述

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。

题目分析

莫队的高级应用 可修改莫队
实质是增加了第三个指针 代表现在已经做完了多少修改
对于每个查询 记录一下在这个查询之前有多少询问 然后在莫队的时候顺便维护一下修改的指针 和莫队一样 在r-- l++ 的时候还要撤销修改

我是不会告诉你这题暴力能过的= =

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int val[10010],num[1001010];
int tot,tim,siz;
struct your
{
    int x,y,tim,id;
    int block;
}a[10010];
int t[10010];
struct my
{
    int x,c,old;
}b[10010];
int cmp(your j,your k)
{
    if(j.block==k.block) return j.y<k.y;
    return j.block<k.block;
}
int now,sum;
int ans[10010];
void add(int x)
{
    sum+=((++num[x])==1);
}
void del(int x)
{
    sum-=((--num[x])==0);
}
int l=1,r=0;
void update(int x,int c)
{
    if(l<=x&&x<=r) add(c),del(val[x]);
    val[x]=c;
}
char s[20];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&val[i]),t[i]=val[i];
    siz=sqrt(1.0*n);
    for(int x,y,i=1;i<=m;i++) 
    {
        scanf("%s",&s[0]);
        if(s[0]=='R')
        {
            scanf("%d%d",&x,&y);
            ++tim,b[tim].x=x,b[tim].c=y,b[tim].old=t[x],t[x]=y;
        }
        else 
        {
            scanf("%d%d",&x,&y);
            ++tot,a[tot].x=x,a[tot].y=y,a[tot].tim=tim;
            a[tot].block=(x-1)/siz,a[tot].id=tot;
        }
    }
    sort(a+1,a+tot+1,cmp);
    for(int i=1;i<=tot;i++)
    {
        while(now<a[i].tim) 
            now++,update(b[now].x,b[now].c);
        while(now>a[i].tim)
            update(b[now].x,b[now].old),now--;
        while(l<a[i].x) del(val[l++]);
        while(r>a[i].y) del(val[r--]);
        while(l>a[i].x) add(val[--l]);
        while(r<a[i].y) add(val[++r]);
        //printf("%d %d\n",a[i].id,sum);
        ans[a[i].id]=sum; 
    }
    for(int i=1;i<=tot;i++) printf("%d\n",ans[i]);
    return 0;
}