题意让你计算每个数左边与它的差的绝对值的最小值。
静态转动态,从左到右依次加入数字。
观察到当前数的最小值一定由当前不大于它的数的最大值和不小于它的数的最小值贡献。
显然其他数和当前数的差都只会更大。
观察到动态“不大/小于……”的范围中的可加性询问,考虑值域上建立树状数组求解。
在值域上建立正反两个树状数组维护信息。
值域略大且有负数,可以平移或者离散化处理。
代码短常数小,吊打平衡树。
#include<bits/stdc++.h>
#define N 32768
#define INF 1145141919
using namespace std;
int n,a[N],id[N],b[N],m,bit1[N],bit2[N],sum;
bool cmp(const int &x,const int &y){return a[x]<a[y];}
void add1(int x,int v){while(x<=m)bit1[x]=max(bit1[x],v),x+=x&-x;}
int q1(int x){int r=-INF;while(x)r=max(bit1[x],r),x-=x&-x;return r;}
void add2(int x,int v){while(x<=m)bit2[x]=min(bit2[x],v),x+=x&-x;}
int q2(int x){int r=INF;while(x)r=min(bit2[x],r),x-=x&-x;return r;}
int main(){
cin>>n;for(int i=1;i<=n;i++)cin>>a[id[i]=i];stable_sort(id+1,id+1+n,cmp);
for(int i=1;i<=n;i++)b[id[i]]=b[id[i-1]]+(i==1||a[id[i]]!=a[id[i-1]]);
m=b[id[n]];
for(int i=0;i<=m;i++)bit1[i]=-INF,bit2[i]=INF;
for(int i=2;i<=n;i++)add1(b[i-1],a[i-1]),add2(m-b[i-1]+1,a[i-1]),
sum+=min(a[i]-q1(b[i]),q2(m-b[i]+1)-a[i]);
cout<<sum+a[1]<<endl;
return 0;
}