题目：https://www.luogu.org/problemnew/show/P2234
学习了一下 treap 的写法。
学习材料：https://blog.csdn.net/litble/article/details/78934306
http://memphis.is-programmer.com/posts/46317.html
https://www.cnblogs.com/AKMer/p/9981274.html
#include<cstdio> #include<cstring> #include<algorithm> #include<ctime> using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } int Mn(int a,int b){return a<b?a:b;} const int N=32770,M=1e9; int n,rt,tot,vl[N],c[N][2],rd[N],ans; void rotate(int &cr,bool d) { int v=c[cr][!d]; c[cr][!d]=c[v][d]; c[v][d]=cr; cr=v; } void ins(int &cr,int k) { if(!cr){cr=++tot; vl[cr]=k; rd[cr]=rand()%M; return;} int d; if(k<=vl[cr]) d=0, ins(c[cr][0],k); else d=1, ins(c[cr][1],k); if(rd[c[cr][d]]>rd[cr])rotate(cr,!d); } int fnd_pr(int cr,int k) { if(!cr)return N; if(vl[cr]<=k) { int d=fnd_pr(c[cr][1],k); return d==N?cr:d; } return fnd_pr(c[cr][0],k); } int fnd_sc(int cr,int k) { if(!cr)return N; if(vl[cr]>=k) { int d=fnd_sc(c[cr][0],k); return d==N?cr:d; } return fnd_sc(c[cr][1],k); } int main() { srand(time(0)); n=rdn(); for(int i=1,d;i<=n;i++) { d=rdn(); if(i==1)ans=d; else { int u=fnd_pr(rt,d), v=fnd_sc(rt,d); if(u==N)ans+=vl[v]-d; else if(v==N)ans+=d-vl[u]; else ans+=Mn(vl[v]-d,d-vl[u]); } ins(rt,d); } printf("%d ",ans); return 0; }