可持久化平衡树

link

fhq 改几个函数就可以了

int refresh(int id) {
    tot++;
    p[tot] = p[id];
    return tot;
}

void split_by_val(int rt, int &a, int &b, int val) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (p[rt].val <= val) {
        a = refresh(rt);//
        split_by_val(p[rt].rs, p[a].rs, b, val);
        pushup(a);//记得是pushup(a)，不是pushup(rt)！！！
    } else {
        b = refresh(rt);//
        split_by_val(p[rt].ls, a, p[b].ls, val);
        pushup(b);//同上，坑了我半个小时
    }
}

void split_by_rank(int rt, int &a, int &b, int rank) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    int ls = p[rt].ls, rs = p[rt].rs;
    if (p[ls].siz + 1 <= rank) {
        a = refresh(rt);//
        split_by_rank(rs, p[a].rs, b, rank - p[ls].siz - 1);
        pushdown(a);
    } else {
        b = refresh(rt);//
        split_by_rank(ls, a, p[b].ls, rank);
        pushdown(b);
    }
}

void merge(int a, int b, int &rt) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (p[a].rnd <= p[b].rnd) {
        rt = refresh(a);
        merge(p[a].rs, b, p[rt].rs);
    } else {
        rt = refresh(b);
        merge(a, p[b].ls, p[rt].ls);
    }
    pushup(rt);
}

因为我的其他函数都有带引用的根节点编号 &rt 所以调用函数的时候加上 root[] 就可以啦
example：
insert(root[i], val) 在第 $i$ 个版本的基础上插入值val，自动更新 root[4] 的值。

实测空间要开到 $3nlog_2(n)$ 大小

代码