题目描述
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
输入输出格式
输入格式：
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
输出格式：
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
输入输出样例
输入样例#1：
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
输出样例#1：
4
4
3
4
说明
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
分析：
这是一道学习新知识的裸题
带修改莫队详细介绍
每个询问节点存储以下信息：
l:左端点
r:右端点
x:在处理这个询问之前，有多少个修改操作
id:编号
每个修改节点存储以下信息：
x:修改位置
y:修改成的值
主程序，统计答案：
我们现在有三个标记：
l,r,x:左端点，右端点，现在处理到了哪个修改
左右端点的转移还是像朴素莫队一样
我这里写了一个update函数
在转移完左右端点之后，
要专门看一下修改操作是否都完成了，
这些都通过一个change操作完成
tip
在给询问编号的时候，不要手滑直接写上i，
一定是专门的询问计数器
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1000010;
int n,m;
int c[N];
struct node1{
int l,r,x,id;
};
node1 q[N];
struct node2{
int x,y;
};
node2 ch[N];
int totq=0,totch=0,unit,ans[N],tot=0;
int sum[N];
int cmp(const node1 &a,const node1 &b)
{
if (a.l/unit!=b.l/unit) return a.l/unit<b.l/unit;
else if (a.r/unit!=b.r/unit) return a.r/unit<b.r/unit;
else return a.x<b.x;
}
void update(int wz,int z)
{
if (z==-1) {
sum[c[wz]]--;
if (!sum[c[wz]]) tot--;
}
else
{
sum[c[wz]]++;
if (sum[c[wz]]==1) tot++;
}
}
void change(int bh,int z,int l,int r)
{
if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,-1); //删除从前的影响
swap(c[ch[bh].x],ch[bh].y);
if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,1); //添加影响
}
void solve()
{
int l=1,r=0,now=0;
for (int i=1;i<=m;i++)
{
while (r<q[i].r) update(r+1,1),r++;
while (r>q[i].r) update(r,-1),r--;
while (l>q[i].l) update(l-1,1),l--;
while (l<q[i].l) update(l,-1),l++;
while (now<q[i].x) change(now+1,1,l,r),now++;
while (now>q[i].x) change(now,-1,l,r),now--;
ans[q[i].id]=tot;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&c[i]);
for (int i=1;i<=m;i++)
{
char s[2];
int x,y;
scanf("%s%d%d",&s,&x,&y);
if (s[0]=='Q')
{
totq++;
q[totq].l=x; q[totq].r=y;
q[totq].x=totch;
q[totq].id=totq;
}
else
{
totch++;
ch[totch].x=x;
ch[totch].y=y;
}
}
unit=(int)sqrt(n);
sort(q+1,q+1+totq,cmp);
solve();
for (int i=1;i<=totq;i++) printf("%d
",ans[i]);
return 0;
}