P2464 [SDOI2008]郁闷的小J

    • 203通过
    • 724提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 各省省选 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小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个整数数A1,A2…AN,Ai表示开始时位置i上的书的编码。

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

    若字符为‘C’,表示图书馆购进新书,后接两个整数A(1<=A<=N),P,表示这本书被放在位置A上,以及这本书的编码为P。

    若字符为‘Q’,表示一个顾客的查询,后接三个整数A,B,K(1<=A<=B<=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<=N,M<=5000

    对于100%的数据,1<=N,M<=100000

    对于100%的数据,所有出现的书的编码为不大于2147483647的正数。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。