[国家集训队]数颜色 / 维护队列

题目描述

墨墨购买了一套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

说明

对于30%的数据,$n,m \leq 10000$ 对于60%的数据,$n,m \leq 50000$ 对于所有数据,$n,m \leq 133333$ 所有的输入数据中出现的所有整数均大于等于1且不超过10^6。 本题可能轻微卡常数 来源:bzoj2120 本题数据为洛谷自造数据,使用[CYaRon](https://github.com/luogu-dev/cyaron)耗时5分钟完成数据制作。