[SDOI2008] 郁闷的小 J

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

小 J 管理一个由 $N$ 个书位组成的书架，书位编号为 $1$ 到 $N$。每个书位恰好放一本书，每本书有一个正整数编码。

他需要处理两类操作：

1. 把某个书位上的书替换为给定编码的新书；
2. 查询一段连续书位中，给定编码的书共有多少本。

请依次回答所有查询。

输入格式

第一行包含两个整数 $N,M$，分别表示书位数和操作数。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，$A_i$ 表示位置 $i$ 上书的初始编码。

接下来 $M$ 行，每行表示一个操作：

• C A P：把位置 $A$ 上的书替换为编码 $P$ 的书；
• Q A B K：查询位置区间 $[A,B]$ 中编码为 $K$ 的书有多少本。

输出格式

对于每个 Q 操作，输出一行一个整数表示答案。

样例输入

5 5
1 2 3 4 5
Q 1 3 2
Q 1 3 1
C 2 1
Q 1 3 2
Q 1 3 1

样例输出

1
1
0
2

数据范围

对于全部数据，$1\le N,M\le10^5$，$1\le A\le B\le N$，修改位置满足 $1\le A\le N$，所有出现的书编码均为不超过 $2^{31}-1$ 的正整数。

所有测试点均独立计分且分值相同。