【Splay】例题

营业额统计

题目背景

HNOI2002 DAY2 T2

题目描述

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

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

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

当最小波动值越大时，就说明营业情况越不稳定。

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

输入格式

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

输出格式

输出一个正整数，即：∑每一天的最小波动值 。结果小于 231 。

样例数据 1

输入

输出

备注

【样例说明】

$5＋|1－5|＋|2－1|＋|5－5|＋|4－5|＋|6－5|＝5＋4＋1＋0＋1＋1＝12$

【题目分析】

裸体求前去后继。

splay最重要的rotate其实就是下面这幅图

【Code】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
;
;

struct node{
    node *fa, *lc, *rc;
    int val;
    node(): fa(NULL), lc(NULL), rc(NULL) {}
}pool[N], *rt = NULL, *tail = pool;

inline int which(node *x){
    return x->fa->rc == x;
}

inline void Rotate(node *x){
    node *y = x->fa, *z = y->fa;
    node *b = y->lc == x ? x->rc : x->lc;
    if(b) b->fa = y;
    (y->lc == x? x->rc : x->lc) = y;
    (y->lc == x ? y->lc : y->rc) = b, y->fa = x;

    if(z) (z->lc == y ? z->lc : z->rc) = x;
    x->fa = z;
}

inline void Splay(node *x, node *tar){
    while(x->fa != tar){
        if(x->fa->fa != tar){
            if(which(x) == which(x->fa)) Rotate(x->fa);
            else Rotate(x);
        }
        Rotate(x);
    }
    if(!tar) rt = x;
}

inline void Insert(int val){
    node *x = rt, *fa = NULL,**p = &rt;
    while(x){
        fa = x;
        if(val < x->val) p = &x->lc, x = x->lc;
        else p = &x->rc, x = x->rc;
    }
    x = tail++;
    x->val = val, x->fa = fa;
    x->lc = x->rc = NULL; *p = x;
    Splay(x, NULL);
}

inline int Query(){
    node *x = rt, *pre, *suf;
    pre = x->lc, suf = x->rc;
    if(pre) while(pre->rc) pre = pre->rc;
    if(suf) while(suf->lc) suf = suf->lc;
    if(!pre) return suf->val - x->val;
    if(!suf) return x->val - pre->val;
    return min(suf->val - x->val, x->val - pre->val);
}

int main(){
    scanf("%d%d", &n, &v);
    ans += v, Insert(v);
    ; i <= n; i++){
        v = ;
        scanf("%d", &v);
        Insert(v);
        ans += Query();
    }
    cout<<ans<<endl;
    ;
}