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

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

const int N = 33000, INF = 0x3f3f3f3f;

struct Node {
    int l, r; //左右儿子的节点号
    int key;  // BST中的真实值
    int val;  //堆中随机值,用于防止链条化
    int size; //小于等于 key的数字个数，用于计算rank等属性
} tr[N];

int root, idx; //用于动态开点，配合tr记录FHQ Treap使用
int x, y, z;   //本题用的三个临时顶点号

void pushup(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1; //合并信息
}

int get_node(int key) {   //创建一个新节点
    tr[++idx].key = key;  //创建一个新点，值为key
    tr[idx].val = rand(); //随机一个堆中索引号
    tr[idx].size = 1;     //新点，所以小于等于它的个数为1个，只有自己
    return idx;           //返回点号
}

//将以p为根的平衡树进行分裂，小于等于key的都放到以x为根的子树中，大于key放到以y为根的子树中
void split(int p, int key, int &x, int &y) {
    if (!p) { //当前节点为空
        x = y = 0;
        return;
    }
    if (tr[p].key <= key)
        x = p, split(tr[p].r, key, tr[p].r, y); // x确定了，左边确定了，但右边未确定，需要继续递归探索
    else
        y = p, split(tr[p].l, key, x, tr[p].l); // y确定了，右边确定了，但左边未确定，需要继续递归探索

    pushup(p); //更新统计信息
}

//将以x，y为根的两个子树合并成一棵树.要求x子树中所有key必须小于等于y子树中所有key
int merge(int x, int y) {
    if (!x || !y) return x + y; //如果x或者y有一个是空了，那么返回另一个即可

    int p;                       //根,返回值
    if (tr[x].val > tr[y].val) { // x.key<y.key,并且, tr[x].val > tr[y].val, x在y的左上，此时理解为大根堆,y向x的右下角合并
        p = x;
        tr[x].r = merge(tr[x].r, y);
    } else {
        p = y;
        tr[y].l = merge(x, tr[y].l); //复读机
    }

    pushup(p); //更新统计信息
    return p;
}

void insert(int key) {
    split(root, key, x, y);                   //按k分割
    root = merge(merge(x, get_node(key)), y); //在x与key节点合并,再与key合并
}

//返回key的前驱，可以和key值一样,此处与上一题不同，上一题要求强制比key小
int get_prev(int key) {
    split(root, key, x, y); //按key分,x最右节点就是前驱
    int p = x;
    while (tr[p].r) p = tr[p].r; //向右走
    int res = tr[p].key;
    root = merge(x, y);
    return res;
}

//返回key的后继
int get_next(int key) {
    split(root, key, x, y); //按key分y最左节点是后继
    int p = y;
    while (tr[p].l) p = tr[p].l;
    int res = tr[p].key;
    root = merge(x, y);
    return res;
}

//创建FHQ Treap带哨兵的空树
void build() {
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2; //+inf > -inf,+inf在-inf右边
    pushup(root);          //更新root的size
}

int main() {
    //加快读入
    ios::sync_with_stdio(false), cin.tie(0);

    //事实证明，套路很重要
    build();

    int n;
    cin >> n;
    int res = 0;
    int x;

    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (i == 1)
            res += x;
        else
            res += min(abs(x - get_prev(x)), abs(get_next(x) - x));
        insert(x);
    }
    printf("%d\n",res);
    return 0;
}

// set ,vector还需要完善，两道题还缺少互相的代码