python/TangDou/AcWing/BalanceTree/265_Treap.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long LL;
const int N = 33010;
const int INF = 0x3f3f3f3f;

// AC 213 ms
int n;
struct Node {
    int l, r;
    int key, val;
    int cnt;
    int size;
} tr[N];

int root, idx;
void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key) {
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

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

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

void insert(int &p, int key) {
    if (!p)
        p = get_node(key);
    else {
        if (tr[p].key == key)
            tr[p].cnt++;
        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);
            }
        }
    }
    pushup(p);
}

// 注意这里与AcWing 253在细节上的区别，那个是严格小于key的最大数
// 找到小于等于key的最大数
int get_prev(int p, int key) {
    if (!p) return -INF;
    if (tr[p].key > key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

// 注意这里与AcWing 253在细节上的区别，那个是严格大于key的最小数
// 找到大于等于key的最小数
int get_next(int p, int key) {
    if (!p) return INF;
    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() {
    //加快读入
    ios::sync_with_stdio(false), cin.tie(0);

    //构建Treap
    build();

    cin >> n;
    LL res = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i == 1)
            res += x;
        else
            res += min(x - get_prev(root, x), get_next(root, x) - x);
        //加入
        insert(root, x);
    }
    //结果
    printf("%lld\n", res);
    return 0;
}