如何用决策单调性分治一定程度代替二分队列？

众所周知，二分队列能做形如 f_{i}=\min\limits_{j<i} f_{j}+w(j,i) 的决策单调性 DP，而决策单调性分治不行，除非套一个 cdq 分治来多一个 \log n 的时间；而当贡献函数 w(l,r) 只能通过类似莫队的方式计算时尤其是还只能回滚时只能用决策单调性分治，而不能用二分队列。

那么我们要做的决策单调性 DP 形如 f_{i}=\min\limits_{j<i} f_{j}+w(j,i) 而且 w(i,j) 只能通过类莫队的转移去计算的时候，我们又该怎么办才能在 O(n\log nP) 的时间内完成一次计算（P 是莫队指针移动的复杂度）？

假设我们计算完了 1\sim r 的 DP 值，而且已知了 r 的决策点 \geq c 的时候，我们可以快速计算出 [r+1,\min(n,r+(r+c-1))] 这一段哪些的决策点范围在 [c,r] 间。

具体地，首先用 [c,r] 一段作为决策点估计 [r+1,\min(n,r+(r+c-1))] 的答案，得到的数组记为 g，显然所有满足决策点在 [r,c] 之间的位置 g 就是最优解了。然后再用 [r+1,\min(n,r+(r+c-1))] 一段的 g 去估计这一段的答案，得到的数组 h。然后将 h 和 g 对应位置两两比对得到第一个 h 比 g 优的位置 t，显然 [r+1,t-1] 位置的 g 数组是最优解，这里得到的 h_{t} 也是最优解，这样可以得到 t 是第一个决策点 >r 的点，显然此时已经算完 [r+1,t] 的答案，直接把 [c,r] 点对改为 [r+1,t] 继续做下去即可。（特殊的，如果 t 不存在就直接把 r 改成 \min(n,r+(r+c-1)) 即可）。

注意到花费了 O(1) 的次数要么让 r 和 r-c+1 都增大了 O(1)，要么让 r-c+1 减少 O(1)，所以总长 O(n)，在每一段里面求 g,h 数组的时候做的都是形如 f_{i}=\min\limits_{j<i} g_{j}+w(j,i) 的 DP，所以可以决策单调性分治，这样复杂度是 O(n\log nP)的，虽然做两遍有两倍常数但决策单调性分治的常数小而且因为分段所以 \log n 跑不太满，所以效率应该比较优秀，不过没测试过就是了，等有时间去做一下效率测试。

这个东西好像就是什么 Wilber 算法？不过 Wilber 算法是线性的，这个只能说是不加 SWAMK 优化的 Wilber 算法。

效率测试方面，在诗人小 G 这道题中这个方法和二分队列时间差别不是很大，在一些点慢 10\sim 20ms，一些点快一些；在邮局加强版加强版中总时间多了快一倍，非常离谱……码量方面二者差不多，本文的方法略长一点但非常好背。

Wilber 的写法：

void divide(int l,int r,int L,int R){
    if(l>r) return;
    int mid=l+r>>1,lim=min(mid-1,R);
    F[mid]=(NODE){G[L].val+calc(L,mid),L};
    rep(i,L+1,lim){
        LD tmp=G[i].val+calc(i,mid);
        if(tmp<F[mid].val) F[mid]=(NODE){tmp,i};
    }
    divide(l,mid-1,L,F[mid].ch),divide(mid+1,r,F[mid].ch,R);
}
void Wilber(){
    int r=0,c=0;
    while(r<n){
        int ri=min(n,r+(r-c+1));
        F=g,G=f,divide(r+1,ri,c,r);
        F=h,G=g,divide(r+2,ri,r+1,ri);
        int t=r+2;
        while(t<=ri&&g[t].val-eps<h[t].val) ++t;
        rep(i,r+1,t-1) f[i]=g[i];
        if(t>ri) r=ri;
        else f[t]=h[t],c=r+1,r=t;
    }
}

二分队列：

head=tail=1;
q[1].c=0,q[1].l=1,q[1].r=n;
for(int i=1;i<=n;++i){
  while(head<tail&&q[head].r<i)head++;
  q[head].l=i;
  int c=q[head].c;
  ch[i]=c;f[i]=f[c]+calc(c,i);//1
  while(head<tail&&cost(i,q[tail].l)<=cost(q[tail].c,q[tail].l))tail--;
  int ll=q[tail].l, rr=q[tail].r+1;
  while(ll<rr){
    int mid=(ll+rr)>>1;
    if(cost(i,mid)<=cost(q[tail].c,mid))rr=mid;
    else ll=mid+1;
  }
  if(ll<=n) q[tail].r=ll-1,q[++tail].c=i,q[tail].l=ll,q[tail].r=n;
}

总结一下毕竟要做两遍决策单调性分治，所以常数非常大，一般情况下还是写二分队列好了，而且在 w(l,r) 只能扫描线的时候也只能二分队列。

不过比如 CF868F 和 P5574 就能把因子 k 换成 \log V 了，可以分别做到 O(n\log n\log V) 和 O(n\log ^2 n\log V)/O(n\sqrt n+n\log n\log V)。