二分队列，用于优化决策单调性动态规划的方法之一

若有方程 $f[i]=min\left\{f[j]+cost(j , i) | j<i\right\}$ ，这种方程一般是经典的切割问题，如果 $f [i]$ 的最佳转移点（也就是那个让 $f [j] + c o s t (j, i)$ 最小的 j）随 i 的增加单调递增，那么此方程就是决策单调的。这个方程本身的时间复杂度是 $o (n^{2})$ ，我们可以利用决策单调性的特性优化到 $o (n l g n)$ 。

为了明白决策单调性带来的特性，我们假设有转移点 j1 与 j2：j1 是当状态为i时的最佳转移点，也就是 $f [i]$ 最后算出的最小值值应该是 $f [j 1] + c o s t (j 1, i)$ ，j2 不是此时的最佳转移点，j2>j1。又因为这个方程具有决策单调性，所以 j2 总会在将来某个状态的时候超过 j1，变成更好的转移点。换句话说，就是当 i 增加到某个临界值时，j1 会被 j2 超车。因为有决策单调性，所以如果给定任意两个转移点的话，它们的这个临界值是可以用二分算出来的。

如何应用这个特性来加速转移点的寻找呢？我们可以维护一个双向队列，队列每个元素是 (k,l,r)：k 表示一个转移点，l 与 r 表示一个状态区间，k 是对于这个区间中的所有状态的最佳转移点（注意这个区间并不是静态的，它会随着状态的推进而更新，后面会细说）。

出队：目前状态为 i，弹出队首直到其区间包含 i，因为如果连 i 都包含不了，那么 i 后面的状态必定包含不了。不能再弹出时，队首元素的 k 就是 $f [i]$ 的最佳转移状态。这样就可以直接算转移方程了。

入队：算好了转移方程，出现了一个新的转移点需要入队，那么有以下情况——

（1）如果队尾转移点k对其区间最左侧（l处）的状态的转移效果比i对此处的转移效果差，也就是 $f [k] + c o s t (k, l) > f [i] + c o s t (i, l)$ （小的效果好），那么直接弹出队尾。可能有多次弹出，直到遇到情况(2)或(3)。这些被删掉的区间不是消失了，它们应该被i的区间包含。

（2）如果i在队尾转移点k的区间最右侧（r处）的转移效果比队尾的转移效果差。那么此时，如果 r<n，将元素 (i,r,n) 入队。右边界是n是为了继承情况(1)中删去的区间。如果 r=n，也就是情况(1)中一个也没删掉， i 就无需入队了。

（3）如果 i 对于队尾转移点k的区间最左侧（l处）状态比队尾 k 差，但对于 r 状态比队尾 k 好，那么需要使用二分算出区间 [l,r] 中，i 比队尾元素 k 好的这个临界状态 $f [p]$ 的 p。然后将队尾元素的r修改为 p-1，将新元素（i,p,n）入队。

注意：因为每个状态都应该有一个最佳转移点，所以当进行到状态i时，队列里的区间合起来应该覆盖 [i+1,n]，不应该有任何空缺。可以用这点检查自己的代码。