【Treap】bzoj1588-HNOI2002营业额统计

一、题目

Description

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

Input

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

Output

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

Sample Input

6
5
1
2
5
4
6

Sample Output

12

HINT

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

顺便附上原题链接→_→Problem1588. -- [HNOI2002]营业额统计

二、代码实现

裸treap，没什么好说的┑(￣Д ￣)┍

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAXN=5e4+10;
const int INF=1e9+1e8;
int n;
struct node
{
    int key,pri,l,r;//关键字、优先级、左儿子编号、右儿子编号
}tr[MAXN];
int root,p,s,ptot;
void query_pre(int k,int x)
{
    if(!k)return;
    if(x<tr[k].key)query_pre(tr[k].l,x);
    else
    {
        p=tr[k].key;
        query_pre(tr[k].r,x);
    }
    return;
}
void query_sub(int k,int x)
{
    if(!k)return;
    if(x>tr[k].key)query_sub(tr[k].r,x);
    else
    {
        s=tr[k].key;
        query_sub(tr[k].l,x);
    }
    return;
}
void turn_left(int &k)
{
    int temp=tr[k].r;
    tr[k].r=tr[temp].l;
    tr[temp].l=k;
    k=temp;
    return;
}
void turn_right(int &k)
{
    int temp=tr[k].l;
    tr[k].l=tr[temp].r;
    tr[temp].r=k;
    k=temp;
    return;
}
void insert(int &k,int x)
{
    if(!k)
    {
        k=++ptot;
        tr[k].key=x;
        tr[k].pri=rand();
        return;
    }
    if(tr[k].key==x)return;
    else if(x<tr[k].key)
    {
        insert(tr[k].l,x);
        if(tr[k].pri<tr[tr[k].l].pri)turn_right(k);
    }
    else 
    {
        insert(tr[k].r,x);
        if(tr[k].pri<tr[tr[k].r].pri)turn_left(k);
    }
    return;
}
int main()
{
    scanf("%d",&n);
    srand(n);
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        if(i==1)ans=x;
        else
        {
            p=-INF,s=INF;
            query_pre(root,x);
            query_sub(root,x);
            ans+=min(x-p,s-x);
        }
        insert(root,x);
    }
    printf("%d\n",ans);
    return 0;
}

弱弱地说一句，本蒟蒻码字也不容易，转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/6236211.html