前置节点

STL

双指针

光标移动

hdu4699

给一个序列，有五种操作：

1、在光标后面插入一个数字，并将光标向后移动一位

2、删除光标前一个数字

3、将光标左移一位

4、将光标右移一位

5、查询前 $x$ 个位置的前缀和的最大值，保证 $x$ 在光标之前

用两个栈来模拟整个序列，以光标位置为分界点，两个栈的栈顶都靠近光标位置，左侧成为 $s_1$，右侧称为 $s_2$。

左移、右移就是将两个栈的栈顶元素弹出并插入对方栈顶。

插入数字：向 $s_1$ 栈顶插入数字。

删除数字：弹出 $s_1$ 栈顶。

前缀和最大值在向 $s_1$ 插入数字时记录。

不删除双指针

双指针问题：

给定一个长度为 $n$ 的序列 $a$，求满足区间和不超过 $k$ 的最大区间长度。

答：双指针。

如果我们枚举 $r$ ，那么 $l$ 单调不减。

每次在答案中新增 $r$ 的贡献，并删除 $l$ 的贡献。

假设新增一个数的时间复杂度是 $O(\alpha )$ ，删除一个数的贡献是 $O(\beta )$。

当 $O(\beta )>O(\alpha )$ 时，称为删除困难。

比如，求区间最小值、最大公约数等情况。

我们以 $gcd$ 为例，将问题改变成：

给定一个长度为 $n$ 的序列 $a$，求满足区间 $gcd$ 不小于 $k$ 的最大区间长度。

设置一个 $m$ ，初始时 $m=1$ 。

维护两个栈 $s_1,s_2$：

$s_1$ 中保存 $a[i]\sim a[m]$ 区间的信息，$i\in [l,m]$，栈顶是 $i=l$。

$s2$ 中保存 $a[m+1]\sim a[i]$ 区间的信息，$i\in [m+1,r]$，栈顶是 $i=r$。

当 $r$ 向右移动时，将 $a[m+1]\sim a[r]$ 的信息（该问题中为最大公约数）插入 $s_2$ 的栈顶。

当 $l$ 向右移动时，将 $a[l]\sim a[m]$ 的信息从 $s_1$ 的栈顶删除。

当查询 $[l,r]$ 的最大公约数时，求两个栈栈顶的数字的最大公约数即可。

而当栈 $s_1$ 被弹空时，令 $m=r$ ，将 $s_2$ 栈中的数字依次弹出，插入 $s_1$。

因为 $s_2$ 中的区间的 $i$ 自顶向下是递减的，而 $s_1$ 栈中的数字自顶向下是递增的，所以依次从 $s_2$ 中弹出并插入 $s_1$ 恰好符合维护顺序。

因为每个元素只进入栈 $s_2$ 一次，进入栈 $s_1$ 一次，所以均摊复杂度仍然是 $O(1)$。

练习题

G. Coprime Segment