P5574 题解
Neutralized
2022-06-05 11:39:13
## $\text{Links}$
[$\text{Problem}$](https://www.luogu.com.cn/problem/P5574)
[$\text{Record}$](https://www.luogu.com.cn/record/76907232)
[$\text{Read This on Cnblogs}$](https://www.cnblogs.com/suitlie/p/16343661.html)
## $\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](https://www.luogu.com.cn/problem/CF868F)，直接开桶，转移和这题类似；
2.[[IOI2014]holiday 假期](https://www.luogu.com.cn/problem/P5892)，用主席树进行转移，比较巧妙，可以一写.
- 事实上这几道题的决策单调性证明比较类似，都是通过区间包含来获得增量的大小关系.
如果证不出来，可以直接用暴力和决策单调性对拍验证. ~~虽然一般是感性理解~~
- 可以尝试把 $\text{BIT}$ 换成单层 $\text{cdq}$ （没试过
## $\text{Code}$
```cpp
#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;
}
```