【题解】可持久化平衡树 可持久化 Leafy Tree Luogu – 3835

https://www.luogu.org/problemnew/show/P3835

题目大意和普通平衡树一题差不多，只不过需要提供历史版本的支持（会指定当前版本由哪个历史版本复制而来）

这题可以用可持久化 Treap 做但我还没试过

（另外 Splay 不能可持久化的原因是它的复杂度是均摊的，替罪羊树也是这个原因）

Leafy Tree 复杂度不是均摊的因此可以可持久化

各种操作不必说，Leafy Tree 可以理解为动态的线段树，因此可持久化的过程和主席树是差不多的，挺好写的，只不过在 rotate 的时候注意对节点进行复制（可持久化）

空间我开了 $2 \times log _ 2 n$倍

跑得还是挺快的，用时不到无旋 Treap 的一半（与 litble 的代码相比）

另外我试验了一下发现论文里的 maintain 写法还是比较优秀的。

代码：

#include <bits/stdc++.h>

#define NS (500005)

using namespace std;

const double alp = 1 - sqrt(2) * 0.5, bta = (1 - alp * 2) / (1 - alp);

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct N {int s[2], d, sz;} e[NS * 40];

int n, root[NS], sz;

int New(int d) // 申请新节点
{
    int a = ++sz;
    e[a].d = d, e[a].sz = 1, e[a].s[0] = e[a].s[1] = 0;
    return a;
}

void pup(int a) // push up
{
    if (!e[a].s[0]) return;
    e[a].sz = e[e[a].s[0]].sz + e[e[a].s[1]].sz;
    e[a].d = e[e[a].s[1]].d;
}

int Mix(int a, int b) // push down
{
    int res = New(e[b].d);
    e[res].s[0] = a, e[res].s[1] = b, pup(res);
    return res;
}

void rot(int a, int q) // 把 a.s[q] 旋到 a 的位置同时保持指针不改变
{
    if (!e[a].s[0]) return;
    int tmp = e[e[a].s[q]].s[q];
    if (q) e[a].s[0] = Mix(e[a].s[0], e[e[a].s[1]].s[0]);
    else e[a].s[1] = Mix(e[e[a].s[0]].s[1], e[a].s[1]);
    e[a].s[q] = tmp;
}

void mt(int a) // maintain
{
    if (!e[a].s[0]) return;
    int q;
    if (e[e[a].s[0]].sz < e[a].sz * alp) q = 1;
    else if (e[e[a].s[1]].sz < e[a].sz * alp) q = 0;
    else return;
    if (e[e[e[a].s[q]].s[q ^ 1]].sz >= e[e[a].s[q]].sz * bta)
    {
        int tmp = e[a].s[q]; e[a].s[q] = New(0), e[e[a].s[q]] = e[tmp]; // 可持久化，但不加似乎也能 AC 八成是数据水了
        rot(e[a].s[q], q ^ 1);
    }
    rot(a, q);
}

void Insert(int d, int& x, int y) // 插入节点
{
    if (!y) {x = New(d); return;}
    x = New(0), e[x] = e[y];
    if (!e[x].s[0])
    {
        e[x].s[0] = New(d), e[x].s[1] = New(e[x].d);
        if (d > e[x].d) swap(e[x].s[0], e[x].s[1]);
    }
    else if (d > e[e[x].s[0]].d)
        Insert(d, e[x].s[1], e[y].s[1]);
    else Insert(d, e[x].s[0], e[y].s[0]);
    pup(x), mt(x);
}

void Erase(int d, int& x, int y) // 删除节点
{
    x = ++sz, e[x] = e[y];
    int q = (d > e[e[x].s[0]].d);
    if (!e[e[x].s[q]].s[0])
    {
        if (e[e[x].s[q]].d != d) return;
        e[x] = e[e[x].s[q ^ 1]];
    }
    else Erase(d, e[x].s[q], e[y].s[q]);
    pup(x), mt(x);
}

int Order(int d, int a) // 求有多少个数比 d 小
{
    if (!e[a].s[0]) return (e[a].d < d);
    if (e[e[a].s[0]].d < d) return Order(d, e[a].s[1]) + e[e[a].s[0]].sz;
    return Order(d, e[a].s[0]);
}

int Kth(int k, int a) // 第 k 大
{
    if (!e[a].s[0]) return e[a].d;
    if (e[e[a].s[0]].sz <= k) return Kth(k - e[e[a].s[0]].sz, e[a].s[1]);
    return Kth(k, e[a].s[0]);
}

int Pre(int d, int a) // 找前驱
{
    if (!e[a].s[0])
    {
        if (e[a].d < d) return e[a].d;
        return -2147483647;
    }
    if (e[e[a].s[0]].d < d) return max(e[e[a].s[0]].d, Pre(d, e[a].s[1]));
    return Pre(d, e[a].s[0]);
}

int Nxt(int d, int a) // 找后继
{
    if (!e[a].s[0])
    {
        if (e[a].d > d) return e[a].d;
        return 2147483647;
    }
    if (e[e[a].s[0]].d > d) return Nxt(d, e[a].s[0]);
    return Nxt(d, e[a].s[1]);
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1, v, o, x; i <= n; i += 1)
    {
        IN(v), IN(o), IN(x), root[i] = root[v];
        if (o == 1) Insert(x, root[i], root[i]);
        else if (o == 2) Erase(x, root[i], root[i]);
        else if (o == 3) printf("%d\n", Order(x, root[i]) + 1);
        else if (o == 4) printf("%d\n", Kth(x - 1, root[i]));
        else if (o == 5) printf("%d\n", Pre(x, root[i]));
        else printf("%d\n", Nxt(x, root[i]));
    }
    return 0;
}