思路:
每次,插入一个点;
然后找前驱后继;
来,上代码:
#include <cmath>
#include <cstdio>
#include <iostream>using namespace std;#define maxn 33000
#define INF 0x7fffffffstruct TreeNodeType {
int w,key,opi,size,ch[];
};
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[]) tree[now].size+=tree[tree[now].ch[]].size;
if(tree[now].ch[]) tree[now].size+=tree[tree[now].ch[]].size;
}inline int getson(int now)
{
return tree[tree[now].opi].ch[]==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^];
tree[tree[now].ch[pos^]].opi=opi;
tree[now].ch[pos^]=opi;
tree[now].opi=fopi;
tree[opi].opi=now;
if(fopi) tree[fopi].ch[tree[fopi].ch[]==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=;
tree[tot].w=tree[tot].size=;
tree[tot].ch[]=tree[tot].ch[]=;
root=tot;
}
else
{
int now=root,opi=;
while()
{
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=;
tree[tot].ch[]=tree[tot].ch[]=;
tree[opi].ch[X>tree[opi].key]=tot;
splay(tot);
break;
}
}
}
}inline int pre()
{
if(tree[root].w>) return tree[root].key;
int now=tree[root].ch[];
if(now==) return INF;
while(tree[now].ch[]) now=tree[now].ch[];
return tree[now].key;
}inline int suc()
{
int now=tree[root].ch[];
if(now==) return INF;
while(tree[now].ch[]) now=tree[now].ch[];
return tree[now].key;
}inline void in(int &now)
{
register int if_z=;now=;
register char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
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 ;
}