题意简述
设 $f(j)=\min_{i=1}^{j-1}\{|x_j-x_i|\}$,求 $\sum_{i=1}^{n}f(i)$,特别的,$f(1)=x_1$。
对于绝对值,尝试分类讨论。
$$\text{1. 若 }x_j \ge x_i\text{,}$$
$$
\begin{aligned}
f(j) &= \min_{i=1}^{j-1} \{ x_j - x_i \} \\
&= x_j - \max_{i=1}^{j-1} \{ x_i \} \\ \\
\end{aligned}
$$
$$\text{2. 若 }x_j \le x_i\text{,}$$
$$
\begin{aligned}
f(j) &= \min_{i=1}^{j-1} \{ x_i - x_j \} \\
&= - x_j - \max_{i=1}^{j-1} \{ - x_i \} \\
\end{aligned}
$$
$$\text{设 }x’=-x,\text{则条件变成若 }x’_j \ge x’_i $$
$$f(j)=x’_j-\max_{i=1}^{j-1}\{ x’_i\}$$
$$\text{与 1. 形式一致}$$
现在考虑怎么维护比第 $j$ 个数早出现且小于等于 $x_j$ 的第一个数。
这是一个很二维偏序的式子($i<j$ 且 $x_i\le x_j$),所以可以用 CDQ 分治 解决。
复杂度 $T(n)=2T(\dfrac{n}{2})+O(n)=O(n\log{n})$
#include <iostream>
using namespace std;
const int N=32768;
const int INF=1<<30;
inline int read()
{
int x=0;bool w=0;char ch=0;
while(ch<'0'|ch>'9'){w|=(ch=='-');ch=getchar();}
while(ch>='0'&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return w?-x:x;
}
struct cdq{int x,tag;}p[N],q[N],tmp[N];int ans[N];
void solve(int l,int r,cdq*a)
{
if(l==r)return;int i=l,m=l+r>>1,j=m+1,tot=l,maxn=-INF;solve(l,m,a);solve(m+1,r,a);
while(i<=m&j<=r)
{
if(a[i].x<=a[j].x)maxn=a[i].x,tmp[tot++]=a[i++];
else ans[a[j].tag]=min(ans[a[j].tag],a[j].x-maxn),tmp[tot++]=a[j++];
}
while(i<=m)tmp[tot++]=a[i++];
while(j<=r)ans[a[j].tag]=min(ans[a[j].tag],a[j].x-maxn),tmp[tot++]=a[j++];
for(i=l;i<=r;i++)a[i]=tmp[i];
}
int main()
{
int n=read(),sum=0;
for(int i=1;i<=n;i++)ans[i]=INF,p[i].tag=q[i].tag=i,p[i].x=read(),q[i].x=-p[i].x;
ans[1]=p[1].x;
solve(1,n,p);solve(1,n,q);
for(int i=1;i<=n;i++)sum+=ans[i];
cout<<sum;
return 0;
}