#P2464. [SDOI2008] 郁闷的小 J
[SDOI2008] 郁闷的小 J
题目描述
小 J 是国家图书馆的一位图书管理员,他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳,但是由于这个书架十分巨大,所以他的工作效率总是很低,以致他面临着被解雇的危险,这也正是他所郁闷的。
具体说来,书架由 个书位组成,编号从 到 。每个书位放着一本书,每本书有一个特定的编码。
小 J 的工作有两类:
-
图书馆经常购置新书,而书架任意时刻都是满的,所以只得将某位置的书拿掉并换成新购的书。
-
小 J 需要回答顾客的查询,顾客会询问某一段连续的书位中某一特定编码的书有多少本。
例如,共 个书位,开始时书位上的书编码为 。
一位顾客询问书位 到书位 中编码为“”的书共多少本,得到的回答为:。
一位顾客询问书位 到书位 中编码为“”的书共多少本,得到的回答为:。
此时,图书馆购进一本编码为“”的书,并将它放到 号书位。
一位顾客询问书位 到书位 中编码为“”的书共多少本,得到的回答为:。
一位顾客询问书位 到书位 中编码为“”的书共多少本,得到的回答为:。
……
你的任务是写一个程序来回答每个顾客的询问。
输入格式
第一行两个整数 ,表示一共 个书位, 个操作。
接下来一行共 个整数数 , 表示开始时位置 上的书的编码。
接下来 行,每行表示一次操作,每行开头一个字符。
若字符为 C
,表示图书馆购进新书,后接两个整数 (),表示这本书被放在位置 上,以及这本书的编码为 。
若字符为 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
提示
对于 的数据,。
对于 的数据,。
对于 的数据,所有出现的书的编码为不大于 的正数。