BZOJ5125: [Lydsy1712月赛]小Q的书架（DP决策单调性）

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=40010;
int a[maxn],sum[maxn],dp[maxn],ans[maxn],N,K,ql,qr,cost;
inline int query(int x){int res=0;while(x){ res+=sum[x]; x-=(-x)&x;} return res;}
inline void add(int x,int val){while(x<=N){ sum[x]+=val; x+=(-x)&x;} }
inline void move(int l,int r)
{
    while(ql>l) cost+=query(a[--ql]-1),add(a[ql],1);
    while(qr<r) cost+=query(N)-query(a[++qr]),add(a[qr],1);
    while(ql<l) add(a[ql],-1),cost-=query(a[ql++]-1);
    while(qr>r) add(a[qr],-1),cost-=query(N)-query(a[qr--]);
}
inline void get(int l,int r,int L,int R)
{
    if(l>r) return ;
    int mid=(l+r)>>1,Mid;
    for(int i=min(R+1,mid);i>L;i--){
        move(i,mid);
        if(dp[i-1]+cost<ans[mid]) {ans[mid]=dp[i-1]+cost; Mid=i-1;}
    }
    get(l,mid-1,L,Mid); get(mid+1,r,Mid,R);
}
int main()
{
    scanf("%d%d",&N,&K);
    rep(i,1,N) scanf("%d",&a[i]);
    rep(i,1,N) ans[i]=ans[i-1]+query(N)-query(a[i]),add(a[i],1);
    ql=1; qr=N; cost=ans[N];
    rep(i,2,K){
        memcpy(dp,ans,sizeof(ans)); //把上一轮的结果复制
        memset(ans,0x3f,sizeof(ans));
        get(1,N,0,N-1);
    }
    printf("%d\n",ans[N]);
    return 0;
}