luoguP1903数颜色（通过一道题认识带修改莫队）

题目描述
墨墨购买了一套N支彩色画笔&＃xff08;其中有些颜色可能相同&＃xff09;&＃xff0c;摆成一排&＃xff0c;你需要回答墨墨的提问。墨墨会像你发布如下指令&＃xff1a;
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求&＃xff0c;你知道你需要干什么了吗&＃xff1f;

输入输出格式

输入格式&＃xff1a;
第1行两个整数N&＃xff0c;M&＃xff0c;分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数&＃xff0c;分别代表初始画笔排中第i支画笔的颜色。
第3行到第2&＃43;M行&＃xff0c;每行分别代表墨墨会做的一件事情&＃xff0c;格式见题干部分。

输出格式&＃xff1a;
对于每一个Query的询问&＃xff0c;你需要在对应的行中给出一个数字&＃xff0c;代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

输入输出样例

输入样例#1&＃xff1a;
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

输出样例#1&＃xff1a;
4
4
3
4

说明
对于100%的数据&＃xff0c;N≤10000&＃xff0c;M≤10000&＃xff0c;修改操作不多于1000次&＃xff0c;所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

分析&＃xff1a;
这是一道学习新知识的裸题
带修改莫队详细介绍
每个询问节点存储以下信息&＃xff1a;
l:左端点
r:右端点
x:在处理这个询问之前&＃xff0c;有多少个修改操作
id:编号

每个修改节点存储以下信息&＃xff1a;
x:修改位置
y:修改成的值

#主程序&＃xff0c;统计答案&＃xff1a;
我们现在有三个标记&＃xff1a;
l,r,x:左端点&＃xff0c;右端点&＃xff0c;现在处理到了哪个修改
左右端点的转移还是像朴素莫队一样
我这里写了一个update函数

在转移完左右端点之后&＃xff0c;
要专门看一下修改操作是否都完成了&＃xff0c;
这些都通过一个change操作完成

#tip
在给询问编号的时候&＃xff0c;不要手滑直接写上i&＃xff0c;
一定是专门的询问计数器

#include
#include
#include
#include
#includeusing namespace std;const int N&＃61;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&＃61;0,totch&＃61;0,unit,ans[N],tot&＃61;0;
int sum[N];int cmp(const node1 &a,const node1 &b)
{if (a.l/unit!&＃61;b.l/unit) return a.l/unit<b.l/unit;else if (a.r/unit!&＃61;b.r/unit) return a.r/unit<b.r/unit;else return a.x<b.x;
}void update(int wz,int z)
{if (z&＃61;&＃61;-1) {sum[c[wz]]--;if (!sum[c[wz]]) tot--;}else{sum[c[wz]]&＃43;&＃43;;if (sum[c[wz]]&＃61;&＃61;1) tot&＃43;&＃43;;}
}void change(int bh,int z,int l,int r)
{if (ch[bh].x>&＃61;l&&ch[bh].x<&＃61;r) update(ch[bh].x,-1); //删除从前的影响 swap(c[ch[bh].x],ch[bh].y); if (ch[bh].x>&＃61;l&&ch[bh].x<&＃61;r) update(ch[bh].x,1); //添加影响
}void solve()
{int l&＃61;1,r&＃61;0,now&＃61;0;for (int i&＃61;1;i<&＃61;totq;i&＃43;&＃43;){while (r<q[i].r) update(r&＃43;1,1),r&＃43;&＃43;;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&＃43;&＃43;;while (now<q[i].x) change(now&＃43;1,1,l,r),now&＃43;&＃43;;while (now>q[i].x) change(now,-1,l,r),now--;ans[q[i].id]&＃61;tot;}
}int main()
{scanf("%d%d",&n,&m);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d",&c[i]);for (int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){char s[2];int x,y;scanf("%s%d%d",&s,&x,&y);if (s[0]&＃61;&＃61;&＃39;Q&＃39;){totq&＃43;&＃43;;q[totq].l&＃61;x; q[totq].r&＃61;y;q[totq].x&＃61;totch;q[totq].id&＃61;totq;}else{totch&＃43;&＃43;;ch[totch].x&＃61;x;ch[totch].y&＃61;y;}}unit&＃61;(int)sqrt(n);sort(q&＃43;1,q&＃43;1&＃43;totq,cmp);solve();for (int i&＃61;1;i<&＃61;totq;i&＃43;&＃43;) printf("%d\n",ans[i]);return 0;
}