P5574 题解

Neutralized · 2022-06-05 11:39:13 · 题解

\text{Links}

\text{Problem}
\text{Record}
\text{Read This on Cnblogs}

\text{Analysis}

有一个朴素dp，语焉不详：

f_{i,k}=min_{j=1}^{i}(f_{j-1,k-1}+calc(j,i))

大力转移， O(n^4k) （大概），期望得分 0 .（

考虑用 \text{BIT} 维护值域求顺序对，再加上用莫队转移的方式求解区间答案，根据不会证明的性质均摊总复杂度是 O(n^2k \log n) ，期望得分 50 .

套上 \text{wqs} 二分可以做到 O(n^2 \log n \log k) ，但是没证过凸性，而且对于 k \le 25 并无太大帮助。就当期望得分 60 吧。

转移方面好像比较优秀了，换个方向优化：
这个式子比较斜率优化或者决策单调性，但是斜优感觉完全不可做，所以如果有决策单调性就可以解决了。
如果 k \gt j 且对于 i ， k 转移优于 j ：
由于 f_{a,b} 第二维的 b 对局面没有影响，暂时忽略；则

f_{k-1}+calc(k,i) \le f_{j-1}+calc(j,i)

若转移目标右移到 i+1 ，则由于 [k,i] \subseteq [j,i] ，有

\Delta calc_k \le \Delta calc_j

这就是说，增量同时也满足 \le ，所以右移后 k 依然不劣于 j .
这样就有决策单调性了，由于单个 f_{i,k} 可以在 O(n \log n) 时间通过上一层转移过来，所以考虑分治结构，每次计算 f_{mid,k} 并记录最优决策点 d_{mid} ，则 [l,mid-1] 部分的决策区间为 [d_l,d_{mid}] ， [mid+1,r] 的决策区间为 [d_{mid},d_r] .（这里的 d_l 和 d_r 为事先确定的决策点左右边界）分别递归进去即可。
可以证明递归总层数为 O(\log n) ，所以总复杂度 O(nk \log^2 n) ，可以通过。

\text{More}

同样利用决策单调性进行分治的题目还有：
1.Yet Another Minimization Problem，直接开桶，转移和这题类似；
2.[IOI2014]holiday 假期，用主席树进行转移，比较巧妙，可以一写.
事实上这几道题的决策单调性证明比较类似，都是通过区间包含来获得增量的大小关系.
如果证不出来，可以直接用暴力和决策单调性对拍验证. ~~虽然一般是感性理解~~
可以尝试把 \text{BIT} 换成单层 \text{cdq} （没试过

\text{Code}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define ri register int
#define ll long long

#define Neutral Shimokitazawa

#define Tp template<class T>
#ifdef Neutral
    const int End=1e6;
    char buf[End],*p1=buf,*p2=buf;
    #define g() (p1==p2&&(p2=(p1=buf)+fread(buf,1,End,stdin),p1==p2)?EOF:*p1++)
#else
    #define g() getchar()
#endif
#define pc(x) putchar(x)
#define isd(x) (x>=48&&x<=57)
namespace SlowIO{
    Tp inline void rd(T &x) {
        x=0; char i=g(); bool f=1;
        while(!isd(i)) f&=(i!='-'),i=g();
        while(isd(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
        x*=((f<<1)-1);
    }
    const int OUT=1e6;
    static char outp[OUT]; int out;
    Tp inline void op(T x){
        out=0; x<0&&(x=-x,pc('-'));
        if(!x){ pc(48); return; }
        while(x) outp[++out]=x%10+48,x/=10;
        while(out) pc(outp[out--]);
    }
    Tp inline void writeln(T x){ op(x);pc('\n'); }
    Tp inline void writesp(T x){ op(x); pc(' '); }
    Tp inline void write(T x,char c=0){ op(x); c&&pc(c); }
}; using namespace SlowIO;

#define N 25001
int n,K,a[N],Mx;
struct BIT{
    ll tr[N]; int lim;
    #define lowbit(x) ((x)&(-x))
    inline void change(int x,int d){while(x<=lim)tr[x]+=d,x+=lowbit(x);}
    inline ll query(int x,ll ret=0){while(x)ret+=tr[x],x-=lowbit(x); return ret;}
}tr; //BIT ...
ll f[26][N];
int cl=1,cr=0; ll tmp;
inline void move(int l,int r){
    while(cl<l){tmp-=tr.query(tr.lim)-tr.query(a[cl]),tr.change(a[cl],-1),++cl;}
    while(cl>l){--cl,tmp+=tr.query(tr.lim)-tr.query(a[cl]),tr.change(a[cl],1);}
    while(cr>r){tmp-=tr.query(a[cr]-1),tr.change(a[cr],-1),--cr;}
    while(cr<r){++cr,tmp+=tr.query(a[cr]-1),tr.change(a[cr],1);}
} //移动两端点计算区间[l,r]答案
inline void solve(int k,int l,int r,int dl,int dr){
    if(l>r) return;
    ri mid=l+r>>1,upd=min(dr,mid),dm=dl;
    move(upd,mid); //移动到待求区间
    for(ri i=upd;i>=dl;--i){
        ll t=tmp+f[k-1][i-1]; //注意move到[i,mid]则从f[i-1]转移
        if(t<f[k][mid]) f[k][mid]=t,dm=i; //记录最优决策点
        if(i==dl) break; //do ...
        --cl,tmp+=tr.query(tr.lim)-tr.query(a[cl]),tr.change(a[cl],1); //把下一位扩进来
    } solve(k,l,mid-1,dl,dm),solve(k,mid+1,r,dm,dr);
}

int main()
{
    rd(n),rd(K);
    for(ri i=1;i<=n;++i)
        rd(a[i]),Mx=max(Mx,a[i]);
    tr.lim=Mx;
    for(ri i=2;i<=K;++i)
        for(ri j=1;j<=n;++j)
            f[i][j]=2147483600;
    for(ri i=1;i<=n;++i)
        f[1][i]=f[1][i-1]+tr.query(a[i]-1),
        tr.change(a[i],1);
    for(ri i=1;i<=n;++i) tr.change(a[i],-1); //记得清空第一层使用的BIT
    for(ri i=2;i<=K;++i) solve(i,1,n,1,n); //对每个k求一遍f[k][i]用于下次转移
    write(f[K][n]);
    return 0;
}