[HNOI 2002]营业额统计

题意

给定n次操作，每次加入一个新数字，并向答案累加其前驱/后继和其差的较小值。

思路

平衡树裸题，而且我们只需要添加，不需要删除，支持查找前驱，后继。

所以说想法很暴，写起来难度也不大。

代码

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int INF=;
struct Node{
    Node *ch[];
    int r,v;
    int cmp(int x) const {
        if(x==v) return -;
        return x>v;
    }
};
void Rotate(Node* &o, int d) {
    Node* k=o->ch[d^];
    o->ch[d^]=k->ch[d];
    k->ch[d]=o;
    o=k;
}
bool Contain(Node* o, int x) {
    while(o!=NULL) {
        int d=o->cmp(x);
        if(d==-) return true;
        else o=o->ch[d];
    }
    return false;
}
void Insert(Node* &o,int x) {
    if(Contain(o,x)) return;
    if(o==NULL) {
        o=new Node();
        o->ch[]=o->ch[]=NULL;
        o->v=x;
        o->r=rand();
    }
    else{
        int d=o->cmp(x);
        Insert(o->ch[d],x);
        if(o->ch[d]->r>o->r) Rotate(o, d^);
    }
}
int findmax(Node* o, int x) {
    if (o==NULL) return INF;
    if (x>=o->v) return findmax(o->ch[],x);
    else return min(o->v,findmax(o->ch[],x));
}
int findmin(Node* o, int x) {
    if (o==NULL) return -INF;
    if (x<=o->v) return findmin(o->ch[],x);
    else return max(o->v,findmin(o->ch[],x));
}
Node *tree;
int main() {
    int n;
    scanf("%d", &n);
    int ans=;
    for(int i=; i<=n; i++) {
        int x; scanf("%d", &x);
        if(Contain(tree, x)) continue;
        Insert(tree, x);
        int mx=findmax(tree, x);
        int mn=findmin(tree, x);
        if(mx+mn==) ans+=x;
        else ans+=min(abs(x-mx),abs(x-mn));
    }
    printf("%d\n", ans);
    return ;
}