原题链接：https://www.luogu.com.cn/problem/P2234
题意：输出每天最小波动值的和，该天的最小波动值=min{|该天以前某一天的营业额-该天营业额|}
思路：Splay裸题
代码：
#include<bits/stdc++.h> #define ls(x) T[x].ch[0] #define rs(x) T[x].ch[1] #define fa(x) T[x].fa #define root T[0].ch[1] using namespace std; const int MAXN=1e6+10,mod=10007,INF=1e9+10; inline char nc() { static char buf[MAXN],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin)),p1==p2?EOF:*p1++; } struct node { int fa,ch[2],val,rec,sum; }T[MAXN]; int tot=0,pointnum=0; void update(int x){T[x].sum=T[ls(x)].sum+T[rs(x)].sum+T[x].rec;} int ident(int x){return T[fa(x)].ch[0]==x?0:1;} void connect(int x,int fa,int how){T[fa].ch[how]=x;T[x].fa=fa;} void rotate(int x) { int Y=fa(x),R=fa(Y); int Yson=ident(x),Rson=ident(Y); connect(T[x].ch[Yson^1],Y,Yson); connect(Y,x,Yson^1); connect(x,R,Rson); update(Y);update(x); } void splay(int x,int to) { to=fa(to); while(fa(x)!=to) { int y=fa(x); if(T[y].fa==to) rotate(x); else if(ident(x)==ident(y)) rotate(y),rotate(x); else rotate(x),rotate(x); } } int newnode(int v,int f) { T[++tot].fa=f; T[tot].rec=T[tot].sum=1; T[tot].val=v; return tot; } void insert(int x) { int now=root; if(root==0) {newnode(x,0);root=tot;}// else { while(1) { T[now].sum++; if(T[now].val==x) {T[now].rec++;splay(now,root);return ;} int nxt=x<T[now].val?0:1; if(!T[now].ch[nxt]) { int p=newnode(x,now); T[now].ch[nxt]=p; splay(p,root);return ; } now=T[now].ch[nxt]; } } } int find(int x) { int now=root; while(1) { if(!now) return 0; if(T[now].val==x) {splay(now,root);return now;} int nxt=x<T[now].val?0:1; now=T[now].ch[nxt]; } } void delet(int x) { int pos=find(x); if(!pos) return ; if(T[pos].rec>1) {T[pos].rec--,T[pos].sum--;return ;} else { if(!T[pos].ch[0]&&!T[pos].ch[1]) {root=0;return ;} else if(!T[pos].ch[0]) {root=T[pos].ch[1];T[root].fa=0;return ;} else { int left=T[pos].ch[0]; while(T[left].ch[1]) left=T[left].ch[1]; splay(left,T[pos].ch[0]); connect(T[pos].ch[1],left,1); connect(left,0,1);// update(left); } } } int rak(int x) { int now=root,ans=0; while(1) { if(T[now].val==x) return ans+T[T[now].ch[0]].sum+1; int nxt=x<T[now].val?0:1; if(nxt==1) ans=ans+T[T[now].ch[0]].sum+T[now].rec; now=T[now].ch[nxt]; } } int kth(int x)//排名为x的数 { int now=root; while(1) { int used=T[now].sum-T[T[now].ch[1]].sum; if(T[T[now].ch[0]].sum<x&&x<=used) {splay(now,root);return T[now].val;} if(x<used) now=T[now].ch[0]; else now=T[now].ch[1],x-=used; } } int lower(int x) { int now=root,ans=-INF; while(now) { if(T[now].val<=x) ans=max(ans,T[now].val);//本处为<=；与模板不同 int nxt=x<=T[now].val?0:1;//这里需要特别注意 now=T[now].ch[nxt]; } return ans; } int upper(int x) { int now=root,ans=INF; while(now) { if(T[now].val>=x) ans=min(ans,T[now].val);//本处为>=；与模板不同 int nxt=x<T[now].val?0:1; now=T[now].ch[nxt]; } return ans; } int main() { int t,ans; cin>>t>>ans; insert(1<<30); insert(-1<<30); insert(ans); t--; while(t--) { int p; cin>>p; int pre=lower(p); int lat=upper(p); ans+=min(abs(pre-p),abs(lat-p)); insert(p); } cout<<ans<<endl; return 0; }