1. 算法介绍
1.1 普通队列
问题：维护一个队列，支持 pop_front 和 push_back，查询队列内所有元素的信息和。保证该信息具有结合律。不保证该信息具有可差分性。
平凡的做法是用线段树或 ST 表维护这种不可差分的信息，然后跑双指针，时间复杂度大部分情况下会比普通双指针多一个 \(\log\)。
而 Baka's Trick / 不带删尺取 / 对顶栈 则通过记录前后缀信息，结合均摊复杂度，在大多数情况下可以将时间复杂度减少一个 \(\log\)。
具体而言，算法本质上是维护了一个对顶栈，来模拟队列的操作：
- 假设有两个栈：\(stk1, stk2\)，\(stk1\) 存出队的元素信息，\(stk2\) 存入队的元素信息。
- 入队时，直接扔到 \(stk2\) 栈顶，并且记录 \(stk2\) 栈内的前缀信息，以方便撤销入栈。
- 出队时：
- 若 \(stk1\) 内仍有元素，则直接出队，回退版本。
- 否则说明 \(stk1\) 内没有元素，将 \(stk2\) 内的元素全部堆进 \(stk1\)。
- 查询时，直接将两个栈的前缀信息合并即可。
因为每个元素最多只会进入一次 \(stk1\)，因此时间复杂度 \(O(nB)\)。其中 \(B\) 指将两个信息合并的复杂度。
三指针的写法和对顶栈本质是一样的，个人感觉对顶栈更直观。
1.2 双端队列
问题：维护一个双端队列，支持 pop_front、pop_back、push_front、push_back，查询队列内所有元素的信息和。保证该信息具有结合律。不保证该信息具有可差分性。
和维护普通队列差不多，但是运用了一些均摊技巧。
发现难点在于删除元素的时候要把两个栈里的元素倒过来又倒回去，时间复杂度可能会爆炸。这里有一种暴力重构的方法可以解决这个问题：每次遇到删除的栈为空的时候，暴力重构另一个栈，使得当前的两个栈大小之差不超过 \(1\)。
时间复杂度依然是 \(O(nB)\) 的。证明可以考虑势能分析，假设 \(\omega\) 表示当前两个栈大小的绝对值之差，则每次 push 操作最多会使得势能增加 \(1\)；而每次删除操作要么使得势能增加 \(1\)，要么将势能降到小于等于 \(1\)。而总共只能增加 \(q\) 的势能，所以时间复杂度依然是 \(O(nB)\) 的。