思路：
每次，插入一个点；
然后找前驱后继；
来，上代码：
#include <cmath> #include <cstdio> #include <iostream> using namespace std; #define maxn 33000 #define INF 0x7fffffff struct TreeNodeType { int w,key,opi,size,ch[2]; }; struct TreeNodeType tree[maxn]; int n,root,tot,X,ans; inline void updata(int now) { tree[now].size=tree[now].w; if(tree[now].ch[0]) tree[now].size+=tree[tree[now].ch[0]].size; if(tree[now].ch[1]) tree[now].size+=tree[tree[now].ch[1]].size; } inline int getson(int now) { return tree[tree[now].opi].ch[1]==now; } inline void rotate(int now) { int opi=tree[now].opi,fopi=tree[opi].opi,pos=getson(now); tree[opi].ch[pos]=tree[now].ch[pos^1]; tree[tree[now].ch[pos^1]].opi=opi; tree[now].ch[pos^1]=opi; tree[now].opi=fopi; tree[opi].opi=now; if(fopi) tree[fopi].ch[tree[fopi].ch[1]==opi]=now; updata(opi),updata(now); } inline void splay(int now) { for(int opi;opi=tree[now].opi;rotate(now)) { if(tree[opi].opi) rotate(getson(now)==getson(opi)?opi:now); } root=now; } inline void insert() { if(!root) { tree[++tot].key=X; tree[tot].opi=0; tree[tot].w=tree[tot].size=1; tree[tot].ch[0]=tree[tot].ch[1]=0; root=tot; } else { int now=root,opi=0; while(1) { if(tree[now].key==X) { tree[now].w++; tree[now].size++; splay(now); break; } opi=now,now=tree[now].ch[X>tree[now].key]; if(!now) { tree[++tot].key=X; tree[tot].opi=opi; tree[tot].w=tree[tot].size=1; tree[tot].ch[0]=tree[tot].ch[1]=0; tree[opi].ch[X>tree[opi].key]=tot; splay(tot); break; } } } } inline int pre() { if(tree[root].w>1) return tree[root].key; int now=tree[root].ch[0]; if(now==0) return INF; while(tree[now].ch[1]) now=tree[now].ch[1]; return tree[now].key; } inline int suc() { int now=tree[root].ch[1]; if(now==0) return INF; while(tree[now].ch[0]) now=tree[now].ch[0]; return tree[now].key; } inline void in(int &now) { register int if_z=1;now=0; register char Cget=getchar(); while(Cget>'9'||Cget<'0') { if(Cget=='-') if_z=-1; Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } now*=if_z; } int main() { in(n),in(X); ans=X,n--,insert(); while(n--) { in(X),insert(); int p=pre(),s=suc(); ans+=min(abs(X-p),abs(s-X)); } cout<<ans; return 0; }