BZOJ5125 小Q的书架（决策单调性+动态规划+分治+树状数组）

　　设f[i][j]为前i个划成j段的最小代价，枚举上个划分点转移。容易想到这个dp有决策单调性，感性证明一下比较显然。如果用单调栈维护决策就不太能快速的求出逆序对个数了，改为使用分治，移动端点时树状数组维护即可，类似莫队的每次都在原有基础上更新。注意更新时先加再减。感觉复杂度非常玄学丝毫不能看出为啥只需要更新nlog次？

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 40010

#define M 11

#define inf 1600000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,a[N],f[M][N],tree[N],l,r,cur;

void add(int k,int x){while (k<=n) tree[k]+=x,k+=k&-k;}

int query(int k){int s=;while (k) s+=tree[k],k-=k&-k;return s;}

void update(int L,int R)

{

    while (r<R) cur+=r-l+-query(a[r+]),add(a[++r],);

    while (l>L) cur+=query(a[l-]),add(a[--l],);

    while (r>R) add(a[r--],-),cur-=r-l+-query(a[r+]);

    while (l<L) add(a[l++],-),cur-=query(a[l-]);

}

void solve(int k,int x,int y,int l,int r)

{

    if (l>r) return;

    int mid=l+r>>,id=min(mid-,y);f[k][mid]=inf;

    for (int i=min(mid-,y);i>=x;i--)

    {

        update(i+,mid);

        if (f[k-][i]+cur<=f[k][mid]) f[k][mid]=f[k-][i]+cur,id=i;

    }

    solve(k,x,id,l,mid-);

    solve(k,id,y,mid+,r);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5125.in","r",stdin);

    freopen("bzoj5125.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();l=,r=;

    for (int i=;i<=n;i++) a[i]=read();

    f[][]=;for (int i=;i<=n;i++) f[][i]=inf;

    for (int j=;j<=m;j++) solve(j,,n-,,n);

    cout<<f[m][n];

    return ;

}