注意：以下代码最后一个点会 T，输入改成快读应该可以过
const int N=5e5+5; int n,m,t; int i,j,k; int a[N]; struct Node { int l,r; int fa,prl,val; //父节点，优先级，值 }node[N]; int root=0,tree=0; //根，节点个数 void zig(int &x) //右旋 { int y=node[x].l; node[x].l=node[y].r; node[y].r=x; x=y; } void zag(int &x) //左旋 { int y=node[x].r; node[x].r=node[y].l; node[y].l=x; x=y; } void insert(int &id,const int w) { if(!id){ id=++tree; node[id].val=w; node[id].prl=rand(); return ; } if(node[id].val>w){ int L=node[id].l; insert(node[id].l,w); if(node[id].prl>node[L].prl) zig(id); } else{ int R=node[id].r; insert(node[id].r,w); if(node[id].prl>node[R].prl) zag(id); } } int query_pre(const int w) //求比 w 小的最大数 { int id=root,ans=-inf; while(id){ if(w>=node[id].val){ ans=node[id].val; id=node[id].r; } else id=node[id].l; } return ans; } int query_suf(const int w) { int id=root,ans=inf; while(id){ if(node[id].val>=w){ ans=node[id].val; id=node[id].l; } else id=node[id].r; } return ans; } int main() { while(~sd(n)){ for(i=1;i<=n;i++) sd(a[i]); int ans=a[1]; insert(root,a[1]); int x,y; for(i=2;i<=n;i++){ x=query_pre(a[i]); y=query_suf(a[i]); ans+=min(a[i]-x,y-a[i]); //dbg(root); insert(root,a[i]); } pd(ans); } //PAUSE; return 0; }
