#2453. 维护队列

维护队列

题目描述

你小时候玩过弹珠吗?

小朋友 A 有一些弹珠,A 喜欢把它们排成队列,从左到右编号为 11NN。为了整个队列鲜艳美观,小朋友想知道某一段连续弹珠中,不同颜色的弹珠有多少。当然,AA 有时候会依据个人喜好,替换队列中某个弹珠的颜色。但是 AA 还没有学过编程,且觉得头脑风暴太浪费脑力了,所以向你来寻求帮助。

输入格式

输入文件第一行包含两个整数 NNMM
第二行 NN 个整数,表示初始队列中弹珠的颜色。
接下来 MM 行,每行的形式为 Q L RR x cQ L R 表示 A 想知道从队列第 LL 个弹珠到第 RR 个弹珠中,一共有多少不同颜色的弹珠,R x c 表示 A 把 xx 位置上的弹珠换成了 cc 颜色。

输出格式

对于每个 Q 操作,输出一行表示询问结果。

2 3
1 2
Q 1 2
R 1 2
Q 1 2

2
1

提示

对于 100%100 \% 的数据,有 1N10000,1M100001 \le N \le 10000, 1 \le M \le 10000,小朋友 A 不会修改超过 10001000 次,所有颜色均用 1110610^6 的整数表示。

题目来源

2011 福建集训