平衡树详解 https://blog.csdn.net/sjystone/article/details/115443239

营业额统计 https://www.acwing.com/problem/content/267/

1.插入一个数
2.找大于等于x的最小数
3.找小于等于x的最大数
-> 最小波动值为min(x - 小于等于x的最大数, 大于等于x的最小数 - x)

若用set
求大于等于x的最小数 lower_bound(x) (返回的是地址)
求小于等于x的最大数 (- - lower_bound(x)) (相当于找大于某数的最小数的前驱)

1.stl版

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

typedef long long LL;
const int INF = 1e7;
set<int> st;
int n;
LL res;

int main()
{
    cin >> n;
    st.insert(INF), st.insert(-INF);
    for ( int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        if ( !i ) res += x;
        else res += min(x - *(-- st.lower_bound(x)), *st.lower_bound(x) - x);
        st.insert(x);
    }
    cout << res;
    return 0;
}

2.手写版

#include <iostream>
#include <ctime>
#include <cstdio>
using namespace std;

typedef long long LL;
const int N = 34000, INF = 1e7;
int n, idx, root;
LL res;
struct Node{
    int l, r, key, val;
} tr[N];

int get_node(int key)
{
    tr[++ idx].key = key;
    tr[idx].val = rand();
    return idx;
}

void build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[root].r = 2;
}

void zig(int &p)
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
}

void zag(int &p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
}

void insert(int &p, int key)
{
    if ( !p ) p = get_node(key);
    else if ( tr[p].key == key ) return;
    else if ( tr[p].key > key ) 
    {
        insert(tr[p].l, key);
        if ( tr[tr[p].l].val > tr[p].val ) zig(p);
    }
    else
    {
        insert(tr[p].r, key);
        if ( tr[tr[p].r].val > tr[p].val ) zag(p);
    }
}

int get_prev(int p, int key)    //找小于等于key的最大数
{
    if ( !p ) return -INF;
    else if ( tr[p].key > key ) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int &p, int key)   //找大于等于key的最小数
{
    if ( !p ) return INF;
    else if ( tr[p].key < key ) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();
    cin >> n;
    for ( int i = 0; i < n; i ++ ) 
    {
        int x;
        scanf("%d", &x);
        if ( !i ) res += x;
        else res += min(x - get_prev(root, x), get_next(root, x) - x);
        insert(root, x);
    }
    cout << res;
    return 0;
}