baka's trick

众所周知，双指针适用于一类固定左端点，右端点具有单调性的问题，由于每个点只会被删一次，所以令加入/删除的时间复杂度为 \(O(B)\)，总时间复杂度 \(O(nB)\)。

而对于一些信息，加入是简单的，但是删除是困难的（例如 gcd、min）等，这时我们考虑 baka's trick 把删除扔掉。

考虑设一个阈值 \(p\)，假设当前双指针两个端点是 \(l,r\)，要维护的信息是 \(f(l,r)\)，我们开两个栈，一个栈维护 \(\forall l\le i\le mid,f(i,mid)\)，另一个栈维护 \(\forall mid<i\le r,f(mid+1,r)\)，当 \(l\) 或者 \(r\) 右移时，我们只需要弹栈就行。要得到 \(f(l,r)\) 时，只需要合并两个栈顶的信息即可。当 \(l\) 移出 \(mid\) 时，令新的 \(mid\) 为原来的 \(r\)，则我们把另一个栈维护的信息从 \(\forall mid<i\le r,f(mid+1,i)\) 重构成 \(\forall mid<i\le r,f(i,r)\)，然后令 \(l\) 为原来的 \(mid\)，\(mid\) 为原来的 \(r\)，然后这个栈就变成维护 \(\forall l\le i\le mid,f(i,mid)\) 的了，以此类推下去。

这样我们只会加入和合并，令加入/合并的时间复杂度为 \(O(C)\)，总时间复杂度 \(O(nC)\)。

一个例子：求 \(l\le r\) 的数量使得 \(\gcd_{i=l}^ra_i\not=1\)。我们要维护的信息是 \(f(l,r)=\gcd(a_l,\cdots,a_r)\)，加入和合并复杂度均为 \(O(\log V)\)，时间复杂度 \(O(n\log V)\)。

一个不太行的例子：求 \(l\le r\) 的数量使得 \([l,r]\) 内的物品做背包（令背包容量为 \(m\)）的最大价值小于等于 \(k\)。我们要维护的信息是 \(f(l,r)=\operatorname{knapsack}(l,\cdots,r)\)，即对区间内物品做背包后的结果。虽然加入的时间复杂度为 \(O(m)\)，但是合并时间复杂度为 \(O(m^2)\)，所以总时间复杂度是 \(O(nm^2)\)，在某些题上可能需要更快的解法。