题解：P5055 【模板】可持久化文艺平衡树

· · 题解

前言

在学习该数据结构之前，建议先使用 FHQ-Treap 完成平衡树、可持久化平衡树和文艺平衡树的模板题。
因为有旋 Treap 会更改父子关系，所以较难实现可持久化。因此，可持久化平衡树通常使用 FHQ-Treap 实现。

实现

假设你已经掌握了 FHQ-Treap 的所有操作。
我们不妨先不考虑可持久化，思考一下这四个操作怎么实现。

操作 1

先分裂出来前 p 个位置所在的子树，再新建一个仅包含要插入的节点的树，最后把三棵树合并在一起即可。
::::info[参考代码]

void insert(int &rtt, int k, ll v)
{
    int l, r;
    split(rtt, k, l, r);
    rtt = merge(merge(l, newnode(v)), r);
}

::::

操作 2

同理，先分裂出所有大于 p 的，再分裂出所有小于 p 的，把这两棵子树合并即可。 ::::info[参考代码]

void del(int &rtt, int x)
{
    int l, r, p;
    split(rtt, x, l, r); //分裂出<=p的，另一半就是大于p的
    split(l, x - 1, l, p);
    rtt = merge(l, r);
}

::::

操作 3

使用和普通文艺平衡树类似的懒标记思想。
同样是先把区间分裂出来后，再对这个区间打上标记。
注意，在下传懒标记时，由于要实现可持久化，所以当前节点的信息不能更改，那么就先复制当前节点，再在复制品上进行下传操作。
同理，分裂和合并函数也要先复制，再操作。 ::::info[下传懒标记和区间翻转参考代码]

void pushdown(int p)
{
    if(tr[p].flag)
    {
        if(ls)
        {
            ls = clone(ls);
            tr[ls].flag ^= 1;
        }
        if(rs)
        {
            rs = clone(rs);
            tr[rs].flag ^= 1;
        }
        swap(ls, rs);
        tr[p].flag = false;
    }
}

void reverse(int &rtt, int l, int r)
{
    int x, y, z;
    split(rtt, r, x, z);
    split(x, l - 1, x, y);
    tr[y].flag ^= 1;
    rtt = merge(merge(x, y), z);
}

:::: ::::info[复制节点参考代码]

int newnode(ll v)
{
    idx ++;
    tr[idx].val = tr[idx].sum = v;
    tr[idx].ran = rand();
    tr[idx].siz = 1;
    return idx;
}

int clone(int x)
{
    idx ++;
    tr[idx] = tr[x];
    return idx;
}

::::

操作 4

这个很好实现，只需要在 pushup 时一起维护一下区间和就可以了。查询时依然是分裂出来区间之后直接输出就可以了。

参考代码

#include<bits/stdc++.h>
#define debug() cout<<"_Liyx_ is tangwang"<<endl
#define endl '\n'
#define ls tr[p].lson
#define rs tr[p].rson
using namespace std;

const int N = 3e7 + 10;
typedef long long ll;
int n;
ll lst;

int rt[N], idx;
struct node{
    int ran, siz, lson, rson;
    bool flag;
    ll sum, val;
}tr[N];

int newnode(ll v)
{
    idx ++;
    tr[idx].val = tr[idx].sum = v;
    tr[idx].ran = rand();
    tr[idx].siz = 1;
    return idx;
}

int clone(int x)
{
    idx ++;
    tr[idx] = tr[x];
    return idx;
}

void pushup(int p)
{
    tr[p].siz = tr[ls].siz + tr[rs].siz + 1;
    tr[p].sum = tr[ls].sum + tr[rs].sum + tr[p].val;
}

void pushdown(int p)
{
    if(tr[p].flag)
    {
        if(ls)
        {
            ls = clone(ls);
            tr[ls].flag ^= 1;
        }
        if(rs)
        {
            rs = clone(rs);
            tr[rs].flag ^= 1;
        }
        swap(ls, rs);
        tr[p].flag = false;
    }
}

void split(int nw, int x, int &l, int &r)
{
    if(!nw) return l = r = 0, void();
    int p = clone(nw);
    pushdown(p);
    if(tr[ls].siz < x)
    {
        l = p;
        split(rs, x - tr[ls].siz - 1, rs, r);
    }else{
        r = p;
        split(ls, x, l, ls);
    }
    pushup(p);
}

int merge(int l, int r)
{
    if(!l || !r) return l + r;
    int p;
    if(tr[l].ran > tr[r].ran)
    {
        p = clone(l);
        pushdown(p);
        rs = merge(rs, r);
    }else{
        p = clone(r);
        pushdown(p);
        ls = merge(l, ls);
    }
    pushup(p);
    return p;
}

void insert(int &rtt, int k, ll v)
{
    int l, r;
    split(rtt, k, l, r);
    rtt = merge(merge(l, newnode(v)), r);
}

void del(int &rtt, int x)
{
    int l, r, p;
    split(rtt, x, l, r);
    split(l, x - 1, l, p);
    rtt = merge(l, r);
}

void reverse(int &rtt, int l, int r)
{
    int x, y, z;
    split(rtt, r, x, z);
    split(x, l - 1, x, y);
    tr[y].flag ^= 1;
    rtt = merge(merge(x, y), z);
}

ll query(int &rtt, int l, int r)
{
    int x, y, z;
    split(rtt, r, x, z);
    split(x, l - 1, x, y);
    ll res = tr[y].sum;
    rtt = merge(merge(x, y), z);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    srand(20070419);
    cin >> n;
    ll v, opt, p, x, l, r;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v >> opt;
        rt[i] = rt[v];
        if(opt == 1)
        {
            cin >> p >> x;
            p ^= lst, x ^= lst;
            insert(rt[i], p, x);
        }else if(opt == 2){
            cin >> p;
            p ^= lst;
            del(rt[i], p);
        }else if(opt == 3){
            cin >> l >> r;
            l ^= lst, r ^= lst;
            reverse(rt[i], l, r);
        }else{
            cin >> l >> r;
            l ^= lst, r ^= lst;
            lst = query(rt[i], l, r);
            cout << lst << endl;
        }
    }

    return 0;
}