当前位置:首页 > 单调队列 > 正文
洛谷P1198[JSOI2008]最大数
1048+

题目大意:对于一个数列,数据慢慢入队,在入队过程中,你能快速回到最后l个数的最大值是多少吗?

题目描述

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

1、 查询操作。

语法:Q L

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

限制:L不超过当前数列的长度。

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]

解题思路

数据一个一个入队,需要查询的时候,遍历最后l个数据,找到最大值并输出,时间复杂度O(m^2),超时。

查询次数是不能改变的,那怎么样才能提高查找的速度呢?剔除不可能是答案的数据。显然,如果后面出现一个比较大的数,那么前面比他小的数都没用了,因为前面那些小的数到最后这个大的数,最大值就是这个比较大的数。因此,我们可以维护这样一个单调递减(不递增也行)的队列。

接着是查询问题,如何快速查询位置i到末尾的最大值(答案)呢?这里介绍两种方法,一种是直接记录该位置的答案,一种是通过二分查找查询答案。

首先是直接记录:如果新入队的数据比前面的大,那么前面的数据的最大值更新为后面那个大的,这样一直往前更新;如果再来一个大的呢?又这样更新的话,显然有很多重复更新的操作。为了避免这个问题,我们可以用并查集把最大值相同的位置合并到一起,并用一个指针记录他前一个不比他小的数据的位置,这样数据就不会重复更新最大值了,如果要更新最大值,只需要更新祖先结点的最大值即可,查询的时候用并查集查询。

其次是二分查找答案:我们可以用一个数组a记录这个单调不递增序列,查询的答案必在这序列里面。现在需要解决的问题是,查询的位置x到末尾这一段区间的最大值。那么x的位置必然在序列中的某两个数据之间。我们可以用一个数组p记录单调队列中数据的原始位置,通过二分查找,找到p[l]<=x<=p[r],x到末尾的最大值一定不比a[r]小,那么什么时候是a[l]呢?当且仅当要查找的位置x恰好是p[l]这个位置。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,,,

洛谷P1198[JSOI2008]最大数:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter