这个也是板子题吧，很水，求前驱后继即可
/*
插入，求前驱和后继
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 1000000
int ch[MAXN][
2],f[MAXN],size[MAXN],cnt[MAXN],key[MAXN];
int sz,root;
inline void clear(
int x){ch[x][
0]=ch[x][
1]=f[x]=size[x]=cnt[x]=key[x]=
0;}
inline bool get(
int x){
return ch[f[x]][
1]==x;}
//判断x是左儿子还是右儿子
inline
void update(
int x){
if(x){
size[x]=
cnt[x];
if(ch[x][
0]) size[x]+=size[ch[x][
0]];
if(ch[x][
1]) size[x]+=size[ch[x][
1]];
}
}
inline void rotate(
int x){
int old=f[x],oldf=f[old],whichx=
get(x);
ch[old][whichx]=ch[x][whichx^
1];
f[ch[old][whichx]]=
old;
ch[x][whichx^
1]=old;f[old]=
x;
f[x]=
oldf;
if(oldf) ch[oldf][ch[oldf][
1]==old]=
x;
update(old);update(x);
}
inline void splay(
int x){
for(
int fa;fa=
f[x];rotate(x))
if(f[fa]) rotate((
get(x)==
get(fa))?
fa:x);
root=
x;
}
inline void insert(
int x){
if(root==
0){root=++sz;ch[sz][
0]=ch[sz][
1]=f[sz]=
0;size[sz]=cnt[sz]=
1;key[sz]=x;
return;}
int now=root,fa=
0;
while(
1){
if(x==key[now]){cnt[now]++;update(now);update(fa);splay(now);
break;}
fa=now;now=ch[now][key[now]<
x];
if(now==
0){
sz++;ch[sz][
0]=ch[sz][
1]=
0;
f[sz]=fa;size[sz]=cnt[sz]=
1;
ch[fa][key[fa]<x]=
sz;
key[sz]=x;
//新建节点
update(fa);splay(sz);
break;
}
}
}
inline int find(
int x){
//寻找x所在位置
int now=root,ans=
0;
while(
1){
if(x<key[now]) now=ch[now][
0];
else {
ans+=(ch[now][
0]?size[ch[now][
0]]:
0);
if(x==key[now]){splay(now);
return ans+
1;}
ans+=
cnt[now];
now=ch[now][
1];
}
}
}
inline int findx(
int x){
//找第x名的值
int now=
root;
while(
1){
if(ch[now][
0] && x<=size[ch[now][
0]]) now=ch[now][
0];
else {
int temp=(ch[now][
0]?size[ch[now][
0]]:
0)+
cnt[now];
if(x<=temp)
return key[now];
x-=temp;now=ch[now][
1];
}
}
}
inline int pre(){
int now=ch[root][
0];
while(ch[now][
1]) now=ch[now][
1];
return now;}
inline int next(){
int now=ch[root][
1];
while(ch[now][
0]) now=ch[now][
0];
return now;}
int main(){
int n,a;
while(scanf(
"%d",&n)==
1){
int ans=
0;
for(
int i=
0;i<n;i++
){
scanf("%d",&
a);
if(i==
0) {insert(a);ans+=
a;}
else {
int tmp=
10000009;
insert(a);
if(cnt[root]>
1)
continue;
if(ch[root][
1])tmp=min(tmp,key[next()]-
a);
if(ch[root][
0])tmp=min(tmp,a-
key[pre()]);
ans+=
tmp;
}
}
printf("%d\n",ans);
}
return 0;
}
View Code
转载于:https://www.cnblogs.com/zsben991126/p/9984677.html
