<!--more-->

分治优化决策单调性

在我们了解的DP方程中，经常会有$f[i]=sum_{max}/sum_{min}/min/max{f[j]+calc(i,j)}$，并且calc(i,j)满足四边形不等式，这种方程存在，而通常情况下，calc(i,j)可以非常轻松的得出，比如说$x^q$，或者sum[i][j],又或者是什么其他的东西。但是，有些时候，我们并不能在$O(logn)/O(1)$的时间内得出，这种情况下，正常通过维护单调队列并且二分的方法就没办法完成了。

这种情况下，我们就需要考虑calc(i,j)的求法了，这种时候，如果我们发现calc(i,j)可以通过分治来均摊$O(nlogn)$处理出来的时候，我们就可以通过整体二分来维护决策单调性来转移，保证整体时间复杂度的正确性。

例题时间

BZOJ 5125: [Lydsy1712月赛]小Q的书架

这道题很显然，我们要将序列分成$K$段使得这$K$段的逆序对和最小。

正常DP方程，f[i][j]=f[i-1][k]+calc(k+1,j);

我们发现calc(k+1,j)满足$calc(i,j)+calc(i-1,j+1) \ge calc(i,j+1)+calc(i+1,j)$所以这个具有决策单调性，但是，我们虽然将DP方程的时间复杂度减少到$O(nklogn)$但是，我们发现，每次计算calc(i,j)还是$O(n)$的，所以总时间复杂度不变，因此，我们考虑用分治优化决策单调性。

我们考虑在整体二分的过程中，calc(i,j)每一层的时间复杂度为$O(n)$，而一共$logn$层，所以时间复杂度为$O(nlogn)$，这样，在DP的同时，calc(i,j)的时间复杂度也降低了，而为了维护calc(i,j)需要用到树状数组求逆序对，所以总时间复杂度为$O(nklog^2n)$显然，是可以做的...

如果K出的大一点的话，我觉得可以带权二分...所以时间复杂度可以达到$O(nlogklog^2n)$，所以还可以加强加强，嗯，就是下一道考试题了！

附上代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define N 40005int f[N],sum[N],g[N],n,k,rl,rr,ret,a[N];void fix(int x,int v){for(;x
             
              l)fix(a[--rl],1),ret+=find(a[rl]-1); while(rr
              
               r)fix(a[rr],-1),ret-=find(n)-find(a[rr--]);}void solve(int l,int r,int L,int R){ if(l>r)return ;int m=(l+r)>>1,p; for(int i=min(m-1,R);i>=L;i--) { get(i+1,m); if(g[i]+ret