思路：
每次，插入一个点；
然后找前驱后继；
来，上代码：
#include#include #include using namespace std;#define maxn 33000#define INF 0x7fffffffstruct 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<