双指针
stripe_python · · 算法·理论
现有指示函数
记
双指针
解决这个问题的经典算法是双指针 / 滑动窗口。我们维护指针
设信息序列
- Push:在
Q 的尾部插入信息。 - Pop:在
Q 的头部弹出信息。 - Check:检查
Q 内信息并的f 值。
for (int l = 1, r = 1; r <= n; r++) {
Q.push(r);
while (l <= r && !Q.check()) Q.pop(), l++;
to[r] = l;
}
可以用队列来实现
-
Push 时右乘新信息,即
\text{sum } \gets \text{sum} \circ x 。 -
Pop 时左乘逆元,即
\text{sum} \gets x^{-1} \circ \text{sum} 。 -
Check 时检查
\text{sum} 是否满足f 的性质。
可以发现,朴素双指针维护的信息需要构成群。
不删双指针
如果信息只构成幺半群,则 Pop 操作失效,我们需要重新设计
维护两个栈
- Push:直接将新元素加入
S_2 。 - Check:当前
Q 的总信息为,S_1 的信息并复合S_2 的信息并。 - Pop:队头对应
S_1 的栈顶。- 若
S_1 非空,直接弹出S_1 的栈顶元素。 - 若
S_1 为空,将S_2 中所有元素依次弹出并加入S_1 ,再弹出S_1 的栈顶。
- 若
由于每个元素只会经历一次