摘自<<洛咕日报>>----浅谈平衡树
模板题洛咕传送门
本题传送门
题意:n个数的序列(a_i),对于第i个元素(a_i),定义(f_i=min{|a_i-a_j|},1<=j<i).其中(f_1=a_1),求(sum f_i).
分析:比模板题码量还低,因为没有删除和查找操作,只有插入,旋转,求前驱后继这几个操作.然后有一个小细节,模板题中的前驱(后继)定义的是:小于(大于)x的最大(最小)的数.而本题的前驱(后继)的意思是:不超过(不小于)x的最大(最小)的数.只要稍稍改动一个符号就可以了.
#include<bits/stdc++.h>
#define N 50000
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
int p,tot,ans;
int num[N],size[N],val[N],rd[N],son[N][2];
void pushup(int p){size[p]=size[son[p][0]]+size[son[p][1]]+num[p];}
void rotate(int &p,int d){
int k=son[p][d^1];
son[p][d^1]=son[k][d];
son[k][d]=p;
pushup(p);pushup(k);p=k;
return;
}
void Insert(int &p,int x){
if(!p){
p=++tot;num[p]=size[p]=1;
val[p]=x;rd[p]=rand();
return;
}
if(val[p]==x){
num[p]++;size[p]++;
return;
}
int d=(val[p]<x);Insert(son[p][d],x);
if(rd[p]<rd[son[p][d]])rotate(p,d^1);
pushup(p);return;
}
int pre(int p,int x){
if(!p)return -1e9;
else if(val[p]>x)return pre(son[p][0],x);
//本来是>=,改成>就可以了
else return max(val[p],pre(son[p][1],x));
}
int nxt(int p,int x){
if(!p)return 1e9;
else if(val[p]<x)return nxt(son[p][1],x);
//本来是<=,改成<就可以了
else return min(val[p],nxt(son[p][0],x));
}
int main(){
int n=read();Insert(p,ans=read());
for(int i=1;i<n;i++){
int x=read();
ans+=min(x-pre(p,x),nxt(p,x)-x);
Insert(p,x);
}
printf("%d
",ans);
return 0;
}