【题解】可持久化文艺平衡树 无旋 Treap Luogu – 5055

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

写了好久啊

看到网上的模板都好奇怪，参数好多好多的，就没看模板瞎写

有几个坑点：

• Copy 节点的时候注意判断你要 Copy 的是不是空节点，Copy 了空节点就 GG 了
• Push Down 的时候两个儿子节点也要可持久化
• 记得输入后异或 last_ans

其实有时候当前访问的节点已经在 Push Down 其父节点的时候可持久化过了，再次 Copy 是对空间的浪费，解决方法有记录每个节点所属的版本号，如果版本号不同就 Copy 一下

然而似乎并不能省下多少个节点，而且记录版本号还需要额外的开销，因此下面的代码中我也就没加这个优化了

节点数即使开了优化开 60 倍都不够，大概要 70 倍，因此在使用 Treap 的时候节点数尽量多开一点，大概要开到 70 倍到 80 倍。。。

代码：

#include <bits/stdc++.h>

#define NS (200005)
#define FIR first
#define SEC second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

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 d, l, r, k, sz; LL s; bool rev;} e[NS * 70];

int n, root[NS], sz;

int New(int d)
{
    int a = ++sz;
    memset(&e[a], 0, sizeof(N));
    e[a].s = e[a].d = d, e[a].k = rand(), e[a].sz = 1;
    return a;
}

int Copy(int x)
{
    if (!x) return 0;
    int a = New(0);
    e[a] = e[x];
    return a;
}

void pup(int a)
{
    e[a].s = e[e[a].l].s + e[e[a].r].s + e[a].d;
    e[a].sz = e[e[a].l].sz + e[e[a].r].sz + 1;
}

void pdown(int a)
{
    if (e[a].rev)
    {
        int &l = e[a].l, &r = e[a].r;
        if (l) l = Copy(l), swap(e[l].l, e[l].r), e[l].rev ^= 1;
        if (r) r = Copy(r), swap(e[r].l, e[r].r), e[r].rev ^= 1;
        e[a].rev = 0;
    }
}

int Merge(int a, int b)
{
    if (!a || !b) return (a | b);
    int c = New(0);
    if (e[a].k < e[b].k) e[c] = e[a], pdown(c), e[c].r = Merge(e[c].r, b);
    else e[c] = e[b], pdown(c), e[c].l = Merge(a, e[c].l);
    pup(c);
    return c;
}

PII Split(int a, int d)
{
    if (!a) return PII(0, 0);
    a = Copy(a), pdown(a);
    int l = e[a].l, r = e[a].r;
    if (e[l].sz == d) {e[a].l = 0, pup(a); return PII(Copy(l), a);}
    if (e[l].sz + 1 == d) {e[a].r = 0, pup(a); return PII(a, Copy(r));}
    if (e[l].sz > d)
    {
        PII tmp = Split(l, d);
        e[a].l = tmp.SEC, pup(a);
        return PII(tmp.FIR, a);
    }
    PII tmp = Split(r, d - e[l].sz - 1);
    e[a].r = tmp.FIR, pup(a);
    return PII(a, tmp.SEC);
}

void Insert(int a, int b, int v)
{
    PII tmp = Split(root[v], a);
    root[v] = Merge(Merge(tmp.FIR, New(b)), tmp.SEC);
}

void Erase(int a, int v)
{
    PII t1 = Split(root[v], a - 1), t2 = Split(t1.SEC, 1);
    root[v] = Merge(t1.FIR, t2.SEC);
}

void Rev(int l, int r, int v)
{
    PII t1 = Split(root[v], l - 1), t2 = Split(t1.SEC, r - l + 1);
    e[t2.FIR].rev ^= 1, swap(e[t2.FIR].l, e[t2.FIR].r);
    root[v] = Merge(t1.FIR, Merge(t2.FIR, t2.SEC));
}

LL lst;

void Query(int l, int r, int v)
{
    int ts = sz, tr = root[v];
    PII t1 = Split(root[v], l - 1), t2 = Split(t1.SEC, r - l + 1);
    printf("%lld\n", lst = e[t2.FIR].s), sz = ts, root[v] = tr;
}

int main(int argc, char const* argv[])
{
    IN(n), srand(19260817);
    for (int i = 1, v, o; i <= n; i += 1)
    {
        LL a, b;
        IN(v), IN(o), IN(a), a ^= lst, root[i] = root[v];
        if (o == 1) IN(b), b ^= lst, Insert(a, b, i);
        else if (o == 2) Erase(a, i);
        else if (o == 3) IN(b), b ^= lst, Rev(a, b, i);
        else IN(b), b ^= lst, Query(a, b, i);
    }
    return 0;
}