经典$Splay$入门题，题意为：有$n$个数，为$a_1,a_2,...,a_n$，定义$S(i)$为$min(a_j) (1 \leq j < i)$，$S(1)=a_1$，求$S(1)+S(2)+...+S(n)$。

这个就是建立一棵$Splay$，然后支持插入，求前驱和后继的操作。

关于$Splay$，以前写过两种，一种是双旋，一种单旋。双旋的有比较麻烦和比较简洁的，我就直接学$n+e$的了。

双旋($n+e$)：

# include <stdio.h>
# define min(a,b) (a<b?a:b)
using namespace std;
// splay
const int Max=100010;
int fa[Max],ch[Max][2],root,data[Max],ind=1;
inline void rotate(int x) {
	// x 节点旋转， opt=1表示右旋， opt=0表示左旋
	int y=fa[x],z=fa[y],p=ch[y][1]==x;
	fa[ch[y][p]=ch[x][p^1]]=y;
	ch[x][p^1]=y;fa[y]=x;fa[x]=z;
	if(z) ch[z][ch[z][1]==y]=x;
}
inline void splay(int x) {
	for (int y;y=fa[x];rotate(x))
		if(fa[y]) rotate((x==ch[y][0])==(y==ch[fa[y]][0])?y:x);
	root=x;
}
inline int pre(int x) {
	int y=ch[x][0];
	while(ch[y][1]) y=ch[y][1];
	return data[y];
}
inline int suc(int x) {
	int y=ch[x][1];
	while(ch[y][0]) y=ch[y][0];
	return data[y];
}
inline void insert(int x,int v) {
	int y;
	while(1) {
		y=ch[x][data[x]<v];
		if(!y) {
			y=++ind;
			data[y]=v;
			ch[y][0]=ch[y][1]=0;
			fa[y]=x;
			ch[x][data[x]<v]=y;
			break;
		}
		x=y;
	}
	splay(y);
}
int n,first,ans=0;
int main() {
	scanf("%d",&n);
	scanf("%d",&first);
	root=1;ch[root][0]=ch[root][1]=0;
	fa[root]=0;data[root]=first;ans=first;
	insert(root,100000000);insert(root,-100000000); 
	for (int i=2;i<=n;++i) {
		int dat=0;scanf("%d",&dat);
		insert(root,dat);
		int a=pre(root),b=suc(root);
		ans+=min(dat-a,b-dat);
	}
	printf("%d\n",ans);
	return 0;
}

双旋：

#include<bits/stdc++.h>
using namespace std;
const int N=40010;
int fa[N],ch[N][2],root,k[N],ind=1;
void zig(int x) {  
    int y=fa[x],z=fa[y];  
    fa[y]=x,fa[x]=z;  
    ch[y][0]=ch[x][1],fa[ch[x][1]]=y,ch[x][1]=y;  
    if (y==ch[z][0]) ch[z][0]=x;  
    else ch[z][1]=x;   
}  
void zag(int x) {  
    int y=fa[x],z=fa[y];  
    fa[y]=x,fa[x]=z; 
    ch[y][1]=ch[x][0],fa[ch[x][0]]=y,ch[x][0]=y;  
    if (y==ch[z][0]) ch[z][0]=x;  
    else ch[z][1]=x;  
}  
void splay(int x,int s) {
    while (fa[x]!=s) {  
        int y=fa[x],z=fa[y];  
        if (z==s) {  
            if (x==ch[y][0]) zig(x);  
            else zag(x);  
            break;  
        }  
        if (y==ch[z][0]) {
            if (x==ch[y][0]) zig(y),zig(x);  
            else zag(x),zig(x);  
        }  
        else {  
            if (x==ch[y][1]) zag(y),zag(x);  
            else zig(x),zag(x);  
        }  
    }  
    if (s==0) root=x;
}  
inline void newnode(int &x,int fax,int key) {
	x=++ind;
	ch[x][0]=ch[x][1]=0;
	fa[x]=fax;
	k[x]=key;
}
inline int search(int w) {
	int p,x=root;
	while(x) {
		p=x;
		if(k[x]>w) x=ch[x][0];
		else x=ch[x][1];
	}
	return p;
}
inline void ins(int w){
	if (root==0) {
		newnode(root,0,w);
		return ;
	}
	int i=search(w);
	if(w<k[i]) newnode(ch[i][0],i,w);
	else newnode(ch[i][1],i,w);
	splay(ind,0);
}
inline int pre(int x) {
	int tmp=ch[x][0];
	while(ch[tmp][1]) tmp=ch[tmp][1];
	return k[tmp];
}
inline int suc(int x) {
	int tmp=ch[x][1];
	while(ch[tmp][0]) tmp=ch[tmp][0];
	return k[tmp];
}
int main() {
	int n,t,ans=0;
	scanf("%d%d",&n,&t);
	root=1;k[root]=t;
	ch[root][0]=ch[root][1]=0;
	fa[root]=0;//printf("hhh");
	ans=t;ins(2100000);
	ins(-2100000);
	for (int i=2;i<=n;++i) {
		if(scanf("%d",&t)==EOF) t=0;
		ins(t);
		int a=pre(root),b=suc(root);
		ans+=min(t-a,b-t);
	}
	printf("%d\n",ans);
	return 0;
}