bzoj1588 营业额统计题解--Treap

Description

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

Input

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

天公司的营业额。

天数n<=32767,

每天的营业额ai <= 1,000,000。

最后结果T<=2^31

Output

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

Sample Input

6
5
1
2
5
4
6

Sample Output

HINT

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

题解

比较水的一道Treap。只要读入一个数，寻找前驱后继并求出最小差值后插入即可。

第一天进行了特殊处理，不过似乎可以优化掉。

代码

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const long long inf=1ll<<32;
struct treap{
    int lc,rc,key,pri,siz,val;
}a[33000];
long long ans,s1,s2;
int n,x,cnt,root;
void pushup(int o){
    a[o].siz=a[a[o].lc].siz+a[a[o].rc].siz+a[o].val;
}
void lturn(int &o){
    int t=a[o].rc;
    a[o].rc=a[t].lc;
    a[t].lc=o;
    a[t].siz=a[o].siz;
    pushup(o);
    o=t;
}
void rturn(int &o){
    int t=a[o].lc;
    a[o].lc=a[t].rc;
    a[t].rc=o;
    a[t].siz=a[o].siz;
    pushup(o);
    o=t;
}
void insert(int k,int &o){
    if(!o){
        o=++cnt;
        a[o]=(treap){0,0,k,rand(),1,1};
        return;
    }
    if(k==a[o].key){
        a[o].val++;
        return;
    }
    a[o].siz++;
    if(k<a[o].key){
        insert(k,a[o].lc);
        if(a[a[o].lc].pri>a[o].pri)rturn(o);
    }
    else{
        insert(k,a[o].rc);
        if(a[a[o].rc].pri>a[o].pri)lturn(o);
    }
    return;
}
void query_pre(int k,int o){
    if(!o)return;
    if(k<a[o].key)query_pre(k,a[o].lc);
    else{
        s1=a[o].key;
        query_pre(k,a[o].rc);
    }
    return;
}
void query_pos(int k,int o){
    if(!o)return;
    if(k>a[o].key)query_pos(k,a[o].rc);
    else{
        s2=a[o].key;
        query_pos(k,a[o].lc);
    }
    return;
}
int main(){
    scanf("%d",&n);
    scanf("%d",&x);
    insert(x,root);
    ans+=x;
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        s1=-inf;
        query_pre(x,root);
        s2=inf;
        query_pos(x,root);
        ans+=min(abs(s1-x),abs(s2-x));
        insert(x,root);
    }
    printf("%lld",ans);
    return 0;
}