luogu#P1903. [国家集训队] 数颜色 / 维护队列

    ID: 5958 远端评测题 1500~2500ms 512MiB 尝试: 50 已通过: 7 难度: 5 上传者: 标签>莫队WC/CTSC/集训队O2优化块状链表块状数组分块

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

题目描述

墨墨购买了一套 NN 支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会向你发布如下指令:

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

  2. R P CR\ P\ C 把第 PP 支画笔替换为颜色 CC

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

输入格式

11 行两个整数 NNMM,分别代表初始画笔的数量以及墨墨会做的事情的个数。

22NN 个整数,分别代表初始画笔排中第 ii 支画笔的颜色。

33 行到第 2+M2+M 行,每行分别代表墨墨会做的一件事情,格式见题干部分。

输出格式

对于每一个 Query 的询问,你需要在对应的行中给出一个数字,代表第 LL 支画笔到第 RR 支画笔中共有几种不同颜色的画笔。

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
4
4
3
4

提示

对于30%的数据,n,m10000n,m \leq 10000

对于60%的数据,n,m50000n,m \leq 50000

对于所有数据,n,m133333n,m \leq 133333

所有的输入数据中出现的所有整数均大于等于 11 且不超过 10610^6

本题可能轻微卡常数

来源:bzoj2120

本题数据为洛谷自造数据,使用 CYaRon 耗时5分钟完成数据制作。