[洛谷P2234][HNOI2002] 营业额统计 - Treap

Description

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

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

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

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

第一天的最小波动值为第一天的营业额。

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

Input&Output

Input

• 第一行为正整数n（n<=32767） ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数ai(|ai|<=1000000) ，表示第i天公司的营业额，可能存在负数。

Output

• 输出一个正整数，每天最小波动值之和，保证答案小于2^31.

Sample

Input

6
5
1
2
5
4
6

Output

12

Solution

找差的绝对值的最小值，可以维护一颗Treap，找当前输入数据的前驱和后缀，取差的绝对值的较小值，加入答案即可。需要注意的是，前驱和后缀的边界条件含等于，因为波动值可以为0。最后我们将当前数据插入Treap即可。本题不需要删除，代码量相对少了一点然而对其他dalao来说并不成问题。

代码如下：

#define _CRT_SECURE_NO_WARNINGS //忽略掉VS的辣鸡设定
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define maxn 32770
#define INF 214700000
using namespace std;
struct node {
    int v, w;
    int l, r;
    int size, k;
    node() {
        l = r = 0;size = k = 0;
    }
}t[maxn];
int rt, cnt, ans, pos, k, n;
void New(int &p, int x)
{
    p = ++cnt;
    t[p].v = x;
    t[p].w = rand();
    t[p].size = t[p].k = 1;
}
void pushup(int p)
{
    t[p].size = t[t[p].l].size + t[t[p].r].size + t[p].k;
}
void turnl(int &p)
{
    int q = t[p].r;
    t[p].r = t[q].l;t[q].l = p;
    p = q;
    pushup(t[p].l);
    pushup(p);
}
void turnr(int &p)
{
    int q = t[p].l;
    t[p].l = t[q].r;t[q].r = p;
    p = q;
    pushup(t[p].r);
    pushup(p);
}
void Insert(int &p, int x)
{
    if (p == 0)
    {
        New(p, x);
        return;
    }
    t[p].size++;
    if (t[p].v == x)
        t[p].k++;
    else if (t[p].v<x) {
        Insert(t[p].r, x);
        if (t[t[p].r].w<t[p].w)turnl(p);
    }
    else {
        Insert(t[p].l, x);
        if (t[t[p].l].w<t[p].w)turnr(p);
    }
}
void pre(int p, int x)
{
    if (p == 0)return;
    else if (x>=t[p].v) {
        pos = p;
        pre(t[p].r, x);
    }
    else pre(t[p].l, x);
}
void suf(int p, int x)
{
    if (p == 0)return;
    else if (x<=t[p].v) {
        pos = p;
        suf(t[p].l, x);
    }
    else suf(t[p].r, x);
}
int main()
{
    int c;
    srand(time(NULL));
    scanf("%d", &n);
    scanf("%d", &c);
    ans += c;
    Insert(rt, c);
    for (int i = 2;i <= n;++i)
    {
        int tmp = INF;
        scanf("%d", &c);
        pos = 0;
        pre(rt, c);
        if (pos != 0)tmp = min(tmp, abs(t[pos].v - c));
        pos = 0;
        suf(rt, c);
        if (pos != 0)tmp = min(tmp, abs(t[pos].v - c));
        Insert(rt, c);
        ans += tmp;
    }
    printf("%d\n", ans);
    return 0;
}