附上奇丑无比的代码：
```
#include<cstdio>
using namespace std;
inline int min(const int &a,const int &b)
{return a<b?a:b;}
inline int abs(const int &x)
{return x<0?-x:x;}
struct splay_tree
{
struct node
{
int val,n,tot,f,son[2];
}tr[110000];
int len,root;
#define xx tr[x]
#define gf tr[f].f
void update(int x)
{xx.tot=tr[xx.son[0]].tot+tr[xx.son[1]].tot+xx.n;}
void add(int val,int fa)
{
tr[++len]=(node){val,1,1,fa,0,0};
tr[fa].son[val>tr[fa].val]=len;
}
void connect(int son,int fa,int dir)
{
tr[fa].son[dir]=son;
if(son)tr[son].f=fa;
}
void rotate(int x,int w)
{
int f=xx.f;
connect(xx.son[w],f,1^w);
connect(x,gf,f==tr[gf].son[1]);
connect(f,x,w);
update(f);
update(x);
}
void splay(int x,int rt)
{
while(xx.f!=rt)
{
int f=xx.f;
if(gf==rt)rotate(x,x==tr[f].son[0]);else
if(tr[gf].son[0]==f&&tr[f].son[0]==x){rotate(f,1);rotate(x,1);}else
if(tr[gf].son[1]==f&&tr[f].son[1]==x){rotate(f,0);rotate(x,0);}else
if(tr[gf].son[0]==f&&tr[f].son[1]==x){rotate(x,0);rotate(x,1);}else
/*if(tr[gf].son[1]==f&&tr[f].son[0]==x)*/{rotate(x,1);rotate(x,0);}
}
if(!rt)root=x;
}
int pos(int val)
{
int x=root;
while(xx.val!=val)
if(val<xx.val)
if(xx.son[0])x=xx.son[0];
else break;
else
if(xx.son[1])x=xx.son[1];
else break;
return x;
}
void ins(int val)
{
if(!len){add(val,0);root=1;return;}
int x=pos(val);
if(xx.val==val)
{
xx.n++;
update(x);
splay(x,0);
}
else
{
add(val,x);
update(x);
splay(len,0);
}
}
int prev(int val)
{
int x=pos(val);splay(x,0);
if(val<xx.val&&xx.son[0])
for(x=xx.son[0];xx.son[1];x=xx.son[1]);
if(val<xx.val)return 0;
return x;
}
int next(int val)
{
int x=pos(val);splay(x,0);
if(val>xx.val&&xx.son[1])
for(x=xx.son[1];xx.son[0];x=xx.son[0]);
if(val>xx.val)return 0;
return x;
}
}tr;
int main()
{
int n,a,ans=0;
scanf("%d",&n);
while(n--)
{
scanf("%d",&a);
int l=tr.prev(a),r=tr.next(a);
if(l)
if(r)
ans+=min(abs(tr.tr[l].val-a),abs(tr.tr[r].val-a));
else
ans+=abs(tr.tr[l].val-a);
else
if(r)
ans+=abs(tr.tr[r].val-a);
else ans+=a;
tr.ins(a);
}
printf("%d",ans);
return 0;
}
```
by MZW_BG @ 2019-07-09 11:53:19
(原题为P2234)
~~完了我觉得我越来越像小学生了~~
by MZW_BG @ 2019-07-09 11:53:58
用内联可以优化
by 樱花飞舞 @ 2019-07-09 11:58:42
@[MZW_BG](/space/show?uid=97504) 封装的话只要没有多态啥的应该也不会太慢吧。窝的LCT似乎速度还行？[记录](https://www.luogu.org/recordnew/show/16080570)
by 小菜鸟 @ 2019-07-09 12:05:55
@[MZW_BG](/space/show?uid=97504) ~~快用指针啊~~
by hovny @ 2019-07-09 12:08:32
~~事实表明我封装的线段树比分块慢QAQ~~
by Nickel_Angel @ 2019-07-09 12:11:03
这个和封装没关系的，总体常数大，自行优化一下吧。
by 小粉兔 @ 2019-07-09 13:03:39
几乎没关系吧
by SSerxhs @ 2019-07-09 13:22:38
connect还封装。。。不t就有鬼了
by SSerxhs @ 2019-07-09 13:23:32
@[SSerxhs](/space/show?uid=29826) 打着好看嘛QAQ
by MZW_BG @ 2019-07-09 13:36:25