题目描述
求数组中每个数前面最接近它的数。
样例
6
5
1
2
5
4
6
12
算法1
(Splay) 均摊$O(nlogn)$
$Splay$板子题。
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
struct SPLAY{
int fa,ch[2],v;
}s[200100];
inline void rotate(int x){
int y=s[x].fa; int z=s[y].fa; int k=s[y].ch[1]==x;
s[z].ch[s[z].ch[1]==y]=x; s[x].fa=z;
s[y].ch[k]=s[x].ch[k^1]; s[s[x].ch[k^1]].fa=y;
s[x].ch[k^1]=y; s[y].fa=x;
}
int ls=1,root;
inline void splay(int x,int goal){
int y,z;
while(s[x].fa!=goal){
y=s[x].fa;z=s[y].fa;
if(z!=goal)
(s[z].ch[1]==y)^(s[y].ch[1]==x)?rotate(x):rotate(y);
rotate(x);
}
if(!goal) root=x;
}
int find(int x){//找到第一个比他大和小的数
int u=root,fa=0;
while(u){
fa=u;
if(s[u].v==x){splay(u,0);fa=u;break;}
if(s[u].v<x) u=s[u].ch[1];
else u=s[u].ch[0];
}
splay(fa,0);//先把找到的数转到根
int k=s[fa].v>x;
u=s[root].ch[k^1];fa=root;
while(u){//然后找另一个数
fa=u;
u=s[u].ch[k];
}
return min(abs(s[root].v-x),abs(s[fa].v-x));
}
void ins(int x){//插入
if(!root){
s[ls].fa=0;
s[ls].ch[0]=s[ls].ch[1]=0;
s[ls].v=x;
ls++;
splay(ls-1,0);
return;
}
int u=root,fa=0;
while(u){
fa=u;
if(s[u].v==x) return;
if(s[u].v>x) u=s[u].ch[0];
else u=s[u].ch[1];
}
s[fa].ch[x>s[fa].v]=ls;
s[ls].fa=fa;
s[ls].ch[0]=s[ls].ch[1]=0;
s[ls].v=x;
ls++;
splay(ls-1,0);
}
void opt(int u){
printf("*****%d %d %d %d\n",u,s[u].ch[0],s[u].ch[1],s[u].v);
if(s[u].ch[0]) opt(s[u].ch[0]);
if(s[u].ch[1]) opt(s[u].ch[1]);
}
int inf=1<<30;
int main(){
int n,x;
long long ans=0;
cin>>n;
for(int i=0;i<n;i++){
scanf("%d",&x);
if(i) ans+=find(x);
else ans=x;
//opt(root);
ins(x);
//printf("**%lld\n",ans);
}
printf("%lld",ans);
return 0;
}