营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值 当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。 ? 输入输出要求

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

 1 #include<cstdio> 2 const int maxn=5e4+10; 3 int n,size; 4 int f[maxn],s[maxn][2],d[maxn]; 5 //f储存父节点编号，s储存左右子，d储存该节点的值。 6 int head,now,up,down,ans; 7 inline int min_(int x,int y){return x<y?x:y;} 8 void rotate(int x,int &k){ 9     int a=f[x],b=f[a],l,r;10     l=s[a][0]==x?0:1;11     r=l^1;12     if(a==k) k=x;13     else{14         if(s[b][0]==a) s[b][0]=x;15         else s[b][1]=x;16     }17     f[x]=b,f[a]=x,f[s[x][r]]=a;18     s[a][l]=s[x][r],s[x][r]=a;19 }20 void splay(int x,int &k){21     int a,b;22     while(x!=k){23         a=f[x],b=f[a];24         if(a!=k){25             if(s[a][0]==x^s[b][0]==a) rotate(x,k);26             else rotate(a,k);27         }28         rotate(x,k);29     }30 }31 void ins(int &k,int x,int fa){32     if(!k){33         size++,k=size;34         d[k]=x,f[k]=fa;35         splay(k,head);36         return;37     }38     if(x<d[k]) ins(s[k][0],x,k);39     else ins(s[k][1],x,k);40 }41 void ask_down(int k,int x){42     if(k==0) return;43     if(d[k]<=x) down=d[k],ask_down(s[k][1],x);44     else ask_down(s[k][0],x);45 }46 void ask_up(int k,int x){47     if(k==0) return;48     if(d[k]>=x) up=d[k],ask_up(s[k][0],x);49     else ask_up(s[k][1],x);50 }51 int main(){52     scanf("%d",&n);53     for(int i=1;i<=n;i++){54         scanf("%d",&now);55         up=1e9,down=-1e9;56         ask_down(head,now);57         ask_up(head,now);58         if(i!=1) ans+=min_(up-now,now-down);59         else ans+=now;60         ins(head,now,0);61     }62     printf("%d\n",ans);63     return 0;64 }