双指针

· · 算法·理论

现有指示函数 f : \mathbb{N}^2 \to \{0,1\} 且 f 满足区间包含单调性

\forall [l_2,r_2] \subseteq [l_1,r_1], f(l_1,r_1) \le f(l_2,r_2)

记 \text{to}_r=\min\limits_{f(l,r)=1} l,求所有的 \text{to}_r。

双指针

解决这个问题的经典算法是双指针 / 滑动窗口。我们维护指针 l,r,枚举 r=1\to n 并令 l \gets l+1 直到 f(l,r)=1,令 \text{to}_r \gets l,复杂度 O(n)。

设信息序列 a_1,a_2,\cdots,a_n。上述算法可视作维护数据结构 Q,进行如下操作:

for (int l = 1, r = 1; r <= n; r++) {
    Q.push(r);
    while (l <= r && !Q.check()) Q.pop(), l++;
    to[r] = l;
}

可以用队列来实现 Q。维护变量 \text{sum} 表示队内的信息并,则:

可以发现,朴素双指针维护的信息需要构成群。

不删双指针

如果信息只构成幺半群,则 Pop 操作失效,我们需要重新设计 Q。

维护两个栈 S_1,S_2,S_1 只负责 pop,S_2 只负责 push。

由于每个元素只会经历一次 S_2 \to S_1 的操作,复杂度均摊 O(n)。维护栈内的前缀信息并即可。