双栈维护头尾操作

是如下的数据结构。

我们需要支持头尾增删，以及全局查询的操作。

蠢笨的做法是使用线段树分治，但会多 \(\log\)，使用双栈可以做到线性。

操作如下：

• 开两个栈 \(stal,star\)，分别处理头尾的增删

• 增：头增 \(stal\)，尾增 \(star\)

• 删：与增类似，但是栈空时特别处理：

  • 双栈大小之和不超过 \(1\) 特判

  • 否则将有数字的那个栈切为两半，均分到两个栈里面 注意顺序，应当是这一半倒着插入另一个栈

• 查：合并两个栈顶信息。

时间复杂度考虑双栈大小之差 \(d\)，显然 \(d\) 增量之和不超过 \(n\)，而减量之和不超过 \(n\)，每次调整会使得 \(d\) 减小一半，均摊同样 \(O(n)\)。

例题：

贪玩蓝月

利用双栈维护背包模板题。

CF2026F

对于 \(1,2,3\) 操作，都新开一个版本，然后建立操作树，这样我们每次进入一个节点都只会进行一个操作，离开时撤销这个操作，利用双栈维护背包即可。