CXXXVI.[IOI2000] 邮局 加强版
Observation 1. 若一段村庄中设一个邮局，则邮局一定设在其中位数（若是偶数则任一中位数）的位置。
Observation 2. 若令 \(w(l,r)\) 为区间 \((l,r)\) 中村庄设一个邮局的费用，则其满足四边形不等式。
Observation 3. 显然全段中修几个邮局的函数有凹性，可以wqs二分。
考虑check二分的 \(mid\)。则我们有转移式
当转移分层时，因为四边形不等式得出的决策单调性，可以分治解决；不分层时，一种解法是使用CDQ分治，正如CXXX.[GYM102904B]Dispatch Money。但是那题囿于逆序对没有 \(O(1)\) 的在线计算方法，所以只能莫队式解决；而本题的 \(w\) 函数是可以简单 \(O(1)\) 在线解决的，因此没有必要使用CDQ分治。
考虑我们当前已经求出了 \(1\sim i\) 所有的 \(f\) 值。此时，位置 \(0\) 转移的位置必定是从 \(i+1\) 开始的一段（当然可能为空），位置 \(1\) 转移的位置必定是紧接着 \(0\) 的转移段后的一段（仍可能为空）……位置 \(i\) 是紧接着 \(i-1\) 的转移段往后一直到结尾的一段。
显然，此时 \(i+1\) 最优转移点已经明确，是从左到右第一个非空的段。但是我们要让其它东西也可以从 \(i+1\) 转移来。
明显，\(i+1\) 转移到的位置必定是一段后缀。于是我们从右往左枚举每一段，若这段最左方的位置从 \(i+1\) 转移更优，显然这一整段都应从 \(i+1\) 转移，然后再判断下一段；否则，就在这段中二分出 \(i+1\) 更优的后缀，然后这段后缀，再加上之前已经判断为 \(i+1\) 转移的那些段，就是 \(i+1\) 的转移段。
这样，内层DP的复杂度就是 \(O(n\log n)\) 的；再套上wqs二分，复杂度就是 \(O(n\log^2n)\) 的。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[500100],F[500100],G[500100],pos[500100],trs[500100],l,r;
ll s[500100],f[500100],g[500100];
ll calc(int l,int r){return s[l-1]+s[r]-s[(l+r)/2]-s[(l+r-1)/2];}
void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int che(ll ip){
// printf("%lld\n",ip);
l=r=1,trs[l]=0;
for(int i=1;i<=n;i++){
if(l<r&&pos[l]==i)l++;
f[i]=f[trs[l]]+calc(trs[l]+1,i)+ip,F[i]=F[trs[l]]+1;
if(i==n)break;
pos[l-1]=i+1,pos[r]=n+1;
while(true){
if(r<l){trs[++r]=i;break;}
if(f[i]+calc(i+1,pos[r-1])<=f[trs[r]]+calc(trs[r]+1,pos[r-1])){r--;continue;}
int L=pos[r-1],R=pos[r];
while(L+1<R){
int mid=(L+R)>>1;
if(f[i]+calc(i+1,mid)<=f[trs[r]]+calc(trs[r]+1,mid))R=mid;
else L=mid;
}
if(R<=n)r++,pos[r-1]=R,trs[r]=i;
break;
}
}
// for(int i=1;i<=n;i++)printf("%lld ",f[i]);puts("");
// for(int i=1;i<=n;i++)printf("%d ",F[i]);puts("");
l=r=1,trs[l]=0;
for(int i=1;i<=n;i++){
if(l<r&&pos[l]==i)l++;
g[i]=g[trs[l]]+calc(trs[l]+1,i)+ip,G[i]=G[trs[l]]+1;
if(i==n)break;
pos[l-1]=i+1,pos[r]=n+1;
while(true){
if(r<l){trs[++r]=i;break;}
if(g[i]+calc(i+1,pos[r-1])<g[trs[r]]+calc(trs[r]+1,pos[r-1])){r--;continue;}
int L=pos[r-1],R=pos[r];
while(L+1<R){
int mid=(L+R)>>1;
if(g[i]+calc(i+1,mid)<g[trs[r]]+calc(trs[r]+1,mid))R=mid;
else L=mid;
}
if(R<=n)r++,pos[r-1]=R,trs[r]=i;
break;
}
}
int R=F[n],L=G[n];
// printf("%d %d\n",L,R);
if(L>m)return 1;
if(R<m)return -1;
printf("%lld\n",f[n]-ip*m);
return 0;
}
int main(){
read(n),read(m);
for(int i=1;i<=n;i++)read(a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
ll l=0,r=1e12,mid;
while(true){
int tp=che(mid=(l+r)>>1);
if(tp==-1)r=mid-1;
if(tp==1)l=mid+1;
if(!tp)break;
}
return 0;
}