P1198 [JSOI2008]最大数

    • 2K通过
    • 6.7K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 二分查找 线段树 各省省选 2008 江苏 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    现在请求你维护一个数列,要求提供以下两种操作:

    1、 查询操作。

    语法:Q L

    功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值。

    限制:L不超过当前数列的长度。(L>=0)

    2、 插入操作。

    语法:A n

    功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列的末尾。

    限制:n是整数(可能为负数)并且在长整范围内。

    注意:初始时数列是空的,没有一个数。

    输入输出格式

    输入格式:

    第一行两个整数,M和D,其中M表示操作的个数(M <= 200,000),D如上文中所述,满足(0<D<2,000,000,000)

    接下来的M行,每行一个字符串,描述一个具体的操作。语法如上文所述。

    输出格式:

    对于每一个查询操作,你应该按照顺序依次输出结果,每个结果占一行。

    输入输出样例

    输入样例#1: 复制
    5 100
    A 96
    Q 1
    A 97
    Q 1
    Q 2
    
    输出样例#1: 复制
    96
    93
    96
    

    说明

    [JSOI2008]

    本题数据已加强

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