营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

           该天的最小波动值= min { |该天以前某一天的营业额-该天营业额| }

当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。

第一行为正整数 ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个正整数 ，表示第i天公司的营业额。

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

6
5 1 2 5 4 6

12

结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12

思路：

treap 模板题 使用treap查找一个数的前驱和后继 关于treap的讲解请移步：传送门

#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
struct your
{
    int l,r,v,rnd;
}a[51000];
int n;
int ans,root,tot;
int befor,aftr;
void lturn(int &k)
{
    int t=a[k].r;
    a[k].r=a[t].l;
    a[t].l=k,k=t;
    /*左旋*/
}
void rturn(int &k)
{
    int t=a[k].l;
    a[k].l=a[t].r;
    a[t].r=k,k=t;
    /*右旋*/
}
void update(int &k,int temp)
{
    if(!k)
    {
        //新建一个叶子节点
        k=++tot;
        a[k].v=temp;
        a[k].rnd=rand();
        return ;
    }
    if(temp<a[k].v)
    {
        update(a[k].l,temp);
        //观察是否满足性质 不满足就旋转
        if(a[a[k].l].rnd<a[k].rnd) rturn(k);
    } 
    else
    {
        update(a[k].r,temp);
        //观察是否满足性质 不满足就旋转
        if(a[a[k].r].rnd<a[k].rnd) lturn(k);
    }
}
void ask_before(int k,int temp)
{
    if(!k) return ;
    if(temp>=a[k].v)
    {
        befor=a[k].v;
        ask_before(a[k].r,temp);
        //进入右节点查询
    }
    else ask_before(a[k].l,temp);
        //进入左节点查询
}
void ask_after(int k,int temp)
{
    if(!k) return ;
    if(temp<=a[k].v)
    {
        aftr=a[k].v;
        ask_after(a[k].l,temp);
        //进入左节点查询
    }
    else ask_after(a[k].r,temp);
        //进入右节点查询
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int tmp;
        if(scanf("%d",&tmp)==EOF) tmp=0;
        befor=-0x7f7f7f7f;
        aftr=0x7f7f7f7f;
        ask_before(root,tmp);
        ask_after(root,tmp);
        if(i>1)ans+=min(tmp-befor,aftr-tmp);
        else ans+=tmp;
        update(root,tmp);
    }
    printf("%d",ans);
}