tyvj P1185 营业额统计

原题链接：http://www.tyvj.cn/p/1185

Treap的应用，具体如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Max_N 40000
#define _min(a,b) ((a)>(b) ? (b) :(a))
#define _abs(x) ((x) < 0 ? (-(x)) : (x))
typedef struct _treap{
    int val, fix;
    struct _treap *ch[];
}treap, *Treap;
treap stack[Max_N];
int sz = ;
int _random(){
    static int x = ;
    x += (x << ) | ;
    return x;
}
void rotate(Treap *x, int c){
    Treap k = (*x)->ch[!c];
    (*x)->ch[!c] = k->ch[c];
    k->ch[c] = *x;
    *x = k;
}
void insert(Treap *x, int val, int fix){
    int d = ;
    if (*x == NULL){
        *x = &stack[sz++];
        (*x)->ch[] = (*x)->ch[] = NULL;
        (*x)->val = val, (*x)->fix = fix;
    } else {
        d = val > (*x)->val;
        insert(&((*x)->ch[d]), val, fix);
        if ((*x)->ch[d]->fix < (*x)->fix) rotate(x, !d);
    }
}
int pre(Treap x, int val){
    int ret = -;
    for (; x != NULL;){
        if (x->val <= val){
            ret = x->val;
            x = x->ch[];
        } else {
            x = x->ch[];
        }
    }
    return ret;
}
int suc(Treap x, int val){
    int ret = -;
    for (; x != NULL;){
        if (x->val >= val){
            ret = x->val;
            x = x->ch[];
        } else {
            x = x->ch[];
        }
    }
    return ret;
}
int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w+", stdout);
#endif
    Treap root = NULL;
    int i, n, t, v1, v2, ans = ;
    scanf("%d", &n);
    for (i = ; i < n; i++){
        scanf("%d", &t);
        if (i == ){
            ans += t;
        } else {
            v1 = pre(root, t), v2 = suc(root, t);
            if (- == v1 || - == v2) ans += (- == v1 ? _abs(v2 - t) : abs(v1 - t));
            else ans += _min(_abs(v1 - t), _abs(v2 - t));
        }
        insert(&root, t, _random());
    }
    printf("%d\n", ans);
    return ;
}