web analytics

单调队列总结

单调队列,顾名思义,就是时刻保持队列单调性。

而满足单调性的队列,就可以用来维护线性移动的动态区间的最值。而题目的下手点,就在 维护什么最值 上下文章。

LuoguP1886 滑动窗口

经典的单调队列题目,就是单调维护最小值与最大值。因为队列满足单调性,所以队列里的值每次都保证是后续有可能的最大值的。

Luogu 1440 求m区间内的最小值

完全一样的题目,可以作为练习题,再手写一遍

Luogu 2629 好消息,坏消息

这道题就不一样了。

首先,为了处理这个顺序,不难看出,可以使用处理环的方式处理这个问题。

其次,判断老板是否心情好,我们可以使用前缀和来解决。

我们就可以发现,判断一种方式是否合法,我们就需要找到这个序列中最小的前缀和,然后减去区间前的那一位前缀和。问题就转变为了维护前缀和中的区间最小值。之后判断就行。