郁闷的小 J(Depressed Little J)

题目描述

小 J 是国家图书馆的一位图书管理员，他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳，但是由于这个书架十分巨大，所以他的工作效率总是很低，以致他面临着被解雇的危险，这也正是他所郁闷的。

具体说来，书架由 $N$ 个书位组成，编号从 $1$ 到 $N$。每个书位放着一本书，每本书有一个特定的编码。

小 J 的工作有两类：

1. 图书馆经常购置新书，而书架任意时刻都是满的，所以只得将某位置的书拿掉并换成新购的书。

2. 小 J 需要回答顾客的查询，顾客会询问某一段连续的书位中某一特定编码的书有多少本。

例如，共 $5$ 个书位，开始时书位上的书编码为 $1, 2, 3, 4, 5$。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$2$”的书共多少本，得到的回答为：$1$。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$1$”的书共多少本，得到的回答为：$1$。

此时，图书馆购进一本编码为“$1$”的书，并将它放到 $2$ 号书位。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$2$”的书共多少本，得到的回答为：$0$。

一位顾客询问书位 $1$ 到书位 $3$ 中编码为“$1$”的书共多少本，得到的回答为：$2$。

……

你的任务是写一个程序来回答每个顾客的询问。

输入格式

第一行两个整数 $N, M$，表示一共 $N$ 个书位，$M$ 个操作。

接下来一行共 $N$ 个整数 $A_1, A_2, \ldots , A_N$，$A_i$ 表示开始时位置 $i$ 上的书的编码。

接下来 $M$ 行，每行表示一次操作，每行开头一个字符。

若字符为 C，表示图书馆购进新书，后接两个整数 $A, P$（$1 \le A \le N$），表示这本书被放在位置 $A$ 上，以及这本书的编码为 $P$。

若字符为 Q，表示一个顾客的查询，后接三个整数 $A, B, K$（$1 \le A \le B \le N$），表示查询从第 $A$ 书位到第 $B$ 书位（包含 $A$ 和 $B$）中编码为 $K$ 的书共多少本。

输出格式

对每一个顾客的查询，输出一个整数，表示顾客所要查询的结果。

样例输入 #1

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
1
0
2

数据范围

对于 $40 \%$ 的数据，$1 \le N, M \le 5000$。

对于 $100 \%$ 的数据，$1 \le N, M \le {10}^5$。

对于 $100 \%$ 的数据，所有出现的书的编码为不大于 $2^{31} - 1$ 的正数。

知识点与难度

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

测试点分布

出处：原题链接