题解：P17319 [ICPC 2018 Nanjing R] Tournament

· · 题解

简化 Larsch 有些烂大街了，这道题都被教练投给学弟做了。
邮局，aliens。

Solution

定义一段连续的房子 a_l\sim a_r 的贡献为：

\begin{aligned} w(l,r)&=\min_{l\le p\le r}\sum_{i=l}^r|a_i-a_p|\\ &=\min_{l\le p\le r}\left(\sum_{i=l}^p(a_p-a_i)+\sum_{i=p+1}^r(a_i-a_p)\right)\\ &=\left(\sum_{i=l}^ra_i\right)+\min_{l\le p\le r}\left(a_p(r-2p+l-1)-2\sum_{i=l}^pa_i\right)\\ &=\mathrm{sum}(l,r)+\min_{l\le p\le r}(r-2p+l-1)a_p-2\mathrm{sum(l,p)} \end{aligned}

其中 \mathrm{sum}(l,r)=\displaystyle\sum_{i=l}^ra_i。固定其他常数，记：

f(p)=(r-2p+l-1)a_p-2\mathrm{sum}(l,p)

于是有差分：

\begin{aligned} \Delta f(p)&=f(p)-f(p-1)\\ &=(r+l-1-2(p-1))(a_p-a_{p-1}) \end{aligned}

由于题目保证了 \{a_n\} 是单调递增的，于是这里的第二个因式 a_p-a_{p-1}>0，只需考虑前面的因式即可。这是一个一次函数，当 \Delta f(p)=0 时取到极值，此时有 p=\left\lceil\dfrac{l+r}{2}\right\rceil，这就是距离和问题的经典结论了。于是 w(l,r)=f\left(\left\lceil\dfrac{l+r}{2}\right\rceil\right)+\mathrm{sum}(l,r)，这就可以 \mathcal O(1) 计算了。

选定若干个地址，求距离和最小，可以转换：将序列划分成 K 段，使得每一段的贡献之和最小。这就是常见的划分 dp 问题了。

我们断言，w(l,r) 是具有凸性的。 :::info[证明]{open} 只需证对于 a\le b\le c\le d，有不等式：

w(a,c)+w(b,d)\le w(a,d)+w(b,c)

恒成立即可。 由于 \left(r+l-1-2\left\lceil\dfrac{l+r}{2}\right\rceil\right)=0 的（或者同值的位置，总之对于某一个决策点一定成立），于是只需要证明不等式：

\mathrm{sum}\left(a,\left\lceil\frac{a+c}{2}\right\rceil\right)+\mathrm{sum}\left(b,\left\lceil\frac{b+d}{2}\right\rceil\right)\ge \mathrm{sum}\left(a,\left\lceil\frac{a+d}{2}\right\rceil\right)+\mathrm{sum}\left(b,\left\lceil\frac{b+c}{2}\right\rceil\right)

移项即证 \square。

再者，使用决策单调性更容易证明，在此不再展开。

这就变成十分经典的 trick 了，外层套一个 WQS 二分，内层使用简化 Larsch。具体的，对于每新加入一个划分，就获得一个惩罚 X，容易发现划分段数关于惩罚 X 是单调的。这就是大名鼎鼎的 WQS 二分。

简化 Larsch 请参考 Noshi91 的博客：簡易版 LARSCH Algorithm。

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=2e6+10,mod=998244353;
typedef pair<int,int> pii;
typedef long long ll;
/*

*/
int C,T=1;
int m,n,k,a[N],sum[N],v;
int w(int l,int r){
    int p=(l+r)>>1;
    return sum[r]-2*sum[p]+sum[l-1]-a[p]*(r-2*p+l-1);
}
int cnt[N],p[N],dp[N],X;
inline void cmin(int u,int v){
    ll x=dp[v]+w(v+1,u)+X;
    if(x<dp[u]) dp[u]=x,p[u]=v,cnt[u]=cnt[v]+1;
    if(x==dp[u]&&cnt[v]+1<cnt[u]) cnt[u]=cnt[v]+1,p[u]=v;
}
void Larsch(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    for(int i=p[l-1];i<=p[r];i++) cmin(mid,i);
    Larsch(l,mid);
    for(int i=l;i<=mid;i++) cmin(r,i);
    Larsch(mid+1,r);
}
bool chk(){
    for(int i=1;i<=n;i++) cnt[i]=p[i]=0,dp[i]=1e15;
    cmin(n,0); Larsch(1,n);
    return cnt[n]<=k;
}
void Lain(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i],sum[i]=sum[i-1]+a[i];
    int B=w(1,n),l=0,r=B,as;
    while(l<r-1) X=(l+r)>>1,chk()?r=X:l=X;
    X=l,chk(),as=dp[n]-l*k;
    X=r,chk(),as=max(as,dp[n]-r*k);
    cout<<as<<"\n";
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
//  cin>>C>>T;
    while(T--) Lain();
    return 0;
}