数颜色 / 维护队列(Counting Colors)

题目描述

墨墨购买了一套 $N$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

1. $Q\ L\ R$ 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。

2. $R\ P\ C$ 把第 $P$ 支画笔替换为颜色 $C$。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入格式

第 $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

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：2000。

测试点分布

出处：原题链接