久仰大名。我曾经看某几位大佬的文章了解到这种算法的存在，但一直没有去学。

在 ABC456F 用到了这个算法，于是简单介绍。

简介

双指针是常用的算法，一个用途是维护滑动窗口内的某种答案，如窗口内的区间最大值。

但一般要求操作可逆。因为我们需要将一些东西移出区间，必须消除它们对记录的答案的影响。

如果操作满足结合律，有时我们可以不使用删除而完成双指针。通过定期完全重构区间答案。

队列

无论目的为何，双指针的滑动窗口总是可以视为一个队列：右边指针右移就是将下一个元素入队，左边指针右移就是将最早加入的元素出队。

我们考虑使用两个栈 s1 和 s2 维护这个队列：加入一个元素时直接加入 s2，弹出一个元素时如果 s1 非空，直接弹出 s1 栈顶；否则我们进行一轮重构：

将 s2 的每个元素依次取出（按从栈顶到栈底的顺序）并压入 s1 的栈顶。

容易证明复杂度是线性的。具体的：每个元素最多入栈两次，出栈两次。

计算答案

仅仅是这样一个奇怪的队列并无用处。但是这个过程中我们可以维护区间信息。

假设我们维护的是从左到右的区间信息，即如果我们的区间是 $[l, r]$，我们要求的是 $\operatorname{op}(a_l, a_{l+1}, \cdots, a_r)$。

对于 s2，我们对其中每个元素维护栈底到它的前缀答案。

对于 s1，刚好反过来：对每个元素维护它到栈底的前缀答案。

说的有点抽象，画个图：

1
2
3
4
5
6
7
8

    栈底            栈顶
s1: [a, b, c, d, ...]
        |
        维护 op(b, a)

s2: [A, B, C, D, ...]
           |
           维护 op(A, B, C)

这样，我们将 s1 与 s2 的栈顶的信息合并起来即可得到区间信息。

顺序是先 s1 后 s2，具体的，假设 s1 栈顶的值是 $x$，s2 栈顶的值是 $y$，则区间答案为 $\operatorname{op}(x, y)$。

维护信息

这比较简单。在压栈时，将之前的栈顶的信息与当前元素的信息按照对应的栈的顺序合并即可。

然后就能解决 456F 了。使用上面的技巧维护区间 $(\min, +)$ 矩阵积。

代码示例