最近学treap，看了cp-algorithm之后就想拿个题练一下，没想到踩了个坑，记录一下

以下为AC代码，道理很简单，就是维护一个平衡排序二叉树，然后不停用二叉树来搜索就行了。我遇到的坑是语法上的坑。

#include <iostream>

using namespace std;

#define debug(x) cout<<#x<<": "<<x<<endl

struct item {
    int key, prior;
    item *l, *r;

    item(int k, int p, item *l, item *r) : key(k), prior(p), l(l), r(r) {}
};

using pitem = item *;

void split(pitem t, int key, pitem &l, pitem &r) {
    if (!t) {
        l = r = nullptr;
    } else if (t->key > key) {
        split(t->l, key, l, t->l);
        r = t;
    } else {
        split(t->r, key, t->r, r);
        l = t;
    }
}

void insert(pitem &t, pitem it) {
    if (!t) t = it;
    else if (it->prior > t->prior) {
        split(t, it->key, it->l, it->r), t = it;
    } else {
        insert(t->key > it->key ? t->l : t->r, it);
    }
}

pitem query_less(pitem t, pitem toq) {
    if (!t)return nullptr;
    if (t->key < toq->key) {
        pitem tr = query_less(t->r, toq);
        return tr ? tr : t;
    } else {
        return query_less(t->l, toq);
    }
}


// use id as prior and fight as key
pitem query_more(pitem t, pitem toq) {
    if (!t)return nullptr;
    if (t->key > toq->key) {
        pitem tl = query_more(t->l, toq);
        return tl ? tl : t;
    } else {
        return query_more(t->r, toq);
    }
}

void pro_sing(pitem &t, pitem it) {
    pitem more = query_more(t, it);
    pitem less = query_less(t, it);
    //debug(more);
    //debug(less);
    pitem to_battle = nullptr;
    if (!more || !less) {
        to_battle = more ? more : less;
    } else if (more->key != less->key) {
        to_battle = (more->key - it->key) < (it->key - less->key) ? more : less;
    } else {
        to_battle = less;
    }

    cout << it->prior << ' ' << to_battle->prior << endl;
    insert(t, it);
}

void solve(int n) {
    static int id, fight;
    pitem t = nullptr;
    insert(t, new item((int) 1e9, 1, nullptr, nullptr));
    while (n--) {
        cin >> id >> fight;
        pro_sing(t, new item(fight, id, nullptr, nullptr));
    }
}

int main() {
    int n;
    while (cin >> n && n) {
        solve(n);
    }
    return 0;
}

坑就在于split函数的当前树指针（第一个参数）如果是引用的话，就会导致树的结构错乱掉。原因，原因在于split函数后面的参数在递归调用的时候有一个是和第一个形参使用了相同的参数，而实际上我们原本是希望这个指针指向一个新的地方，而旧的指针（所指向的那个子树）被接到别的地方。但是由于它们同时使用了引用，在下一个函数栈帧内的 t 和 l/r中的一个实际上是指向了同一块内存，而如果修改了 l/r的话就会导致 t 的变化，而实际上我们是希望旧的t值被赋给 l/r 中的另一个，但是此时旧值已经没了，在上一个栈帧访问到的t实际上已经是改过的了，所以树的结构出错。这个错误太奇葩了，我自己没看出来，给学长看了学长才给我讲懂QAQ