不单调的单调队列

前言

单调队列的用处非常广泛!

今天也要加油哦ヾ(◍°∇°◍)ノ゙

定义

维护一个队列,使其保持降序或升序状态。

queue:队列数组。

head:队列头下标。

tail:队列尾下标。

例题

洛谷P1886 滑动窗口 /【模板】单调队列

单调队列模板题,维护两个队列,一个升序一个降序。

每次先将不在范围内的元素出队,即 head++

再维护单调性,将破坏单调性的去除,即 tail--

然后入队:queue[++tail]=i。(入队的要为原数组下标)

最值即为队头:queue[head]

洛谷P1714 切蛋糕

暴力做法:前缀和,再枚举起点终点求最值即可。

但这显然会超时。

对于每一个前缀和 sumisum_i,以这个为结尾的最大值就为它减去前面区间的最小值,即 sumimin(sumj)(i[]1<j<i)sum_i - min(sum_{j}) (i-[区间长度]-1<j<i)

所以用一个单调队列维护最小值即可。

洛谷P2698 [USACO12MAR]Flowerpot S

我们用两个优先队列,一个存区间最大值,一个存区间最小值。

最外层循环拉左端点(因为要里面右端点移完再动左端点)

每次先用两个while循环更新队首,直到队首不在左端点左边(因为移动了左端点有一个点的值就不能用了)

然后第二层循环移动右端点,直到达到右边界或满足条件(最大值-最小值 > d)。

里面再用两个循环类似滑动窗口更新最大值队列和最小值队列(只要队中还有元素且新加入的元素比队尾大(维护最大值时为小)那么就队尾出队,不需要管队首出队(这是更新左端点做的事情))。

第二层循环结束后,如果满足条件就更新 ansans 。(ansans 要初始化成一个很大的值)。

一切结束后如果 ansans 还是初始值,就输出 “-1”,否则输出 ansans

总结

用单调队列优化DP非常常见。

题单就放在这里啦:link