1 条题解

  • 0
    @ 2025-8-24 22:06:38

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar KevinYu
    **

    搬运于2025-08-24 22:06:38，当前版本为作者最后更新于2018-12-26 18:48:14，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

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

    <Part0.前言>

    对于我们的所求，这一题的题目已经说的很清楚了。
    在题解的正题开始之前，先放几个链接:
    Luogu P3369 普通平衡树
    Luogu P3391 文艺平衡树(Splay)
    Luogu P3835 可持久化平衡树
    建议试着用FHQ Treap(非旋转Treap)来实现这几题。

    </Part 0前言>

    <Part1.FHQ Treap>

    你看啊，这个数据结构的常数比Splay小，理解起来比Splay容易，长得比Splay好看，能实现的东西并不比Splay少，代码量比Splay小，还能可持久化，为什么不学学呢?

    会FHQ Treap的可以跳过了。
    所谓的FHQ Treap其实是一种加强版的Treap。与一般的Treap树不同，FHQ Treap不依赖旋转操作保持自身结构的平衡，而是依赖分裂和合并操作维持树的平衡性质。
    我们先来介绍一下关键操作:
    1.创建新的节点(new_node):
    很简单，就是创建一个新的点，没什么好说的。
    返回当前点的下标。

    inline int new_node(long long v=0)
{
	static int tot(0);
	tpi.val=v;tp.sum=v;
	tp.rand=rand();tp.size=1;
	return tot;
}

    2.复制节点(copy_node):
    也没什么好说的，仅仅是为了方便。
    返回复制后的点的下标。

    inline int copy_node(int p)
{
	int ret=new_node();
	tree[ret]=tree[p];
	return ret;
}

    3.更新(push_up):
    push_up(p)代表更新下标为p的节点。

    inline void push_up(int p)
{
	tree[p].size=tls(p).size+trs(p).size+1;
	tree[p].sum=tls(p).sum+trs(p).sum+t(p).val;
}

    4.标记下传(push_down):
    push_down(p)代表将下标为p的点的标记下传。
    什么标记呢?自然是翻转标记。
    注意:传之前的点别扔了，留着可持久化呢。

    inline void push_down(int p)
{
	if(!t(p).tag)return;
	if(ls(p))ls(p)=copy_node(ls(p));
	if(rs(p))rs(p)=copy_node(rs(p));
	swap(ls(p),rs(p));
	if(ls(p))tls(p).tag^=1;
	if(rs(p))trs(p).tag^=1;
	tree[p].tag=0;
}

    5.分裂(Split):
    这个词我经常打成Spilt。
    所谓的"分裂"，就是将一颗Treap分成两部分。
    你可以理解成，你拿着一个选择性透过膜来"过滤"一颗Treap的过程，最后会将一颗Treap过滤成两个部分。
    我们定义split(p,k,x,y)代表将根为p的子树分为两部分，其中的一部分size为k。
    具体实现起来就是左子树的size还够用的时候，就往左子树递归，不够用的话就往右子树递归。
    先推标记，再分裂!!!!
    Split操作完整代码:

    void split(int p,int k,int &x,int &y)
{
	if(!p){x=y=0;return;}
	push_down(p);
	if(tls(p).size<k){x=copy_node(p);split(rs(x),k-tls(p).size-1,rs(x),y);push_up(x);}
	else{y=copy_node(p);split(ls(y),k,x,ls(y));push_up(y);}
}

    6.合并(Merge):
    合并就更好理解了，就是把两棵子树树合并到一个根节点上。
    跟一般的平衡树一样，我们需要以它们的键值大小关系决定怎么合并它们。(键值怎么得到?rand()了解一下)
    返回值为他们的根节点。
    先推标记，再合并!!!!

    int merge(int x,int y)
{
	if(!x||!y)return x|y;
	push_down(x);push_down(y);
	if(t(x).rand<t(y).rand){rs(x)=merge(rs(x),y);push_up(x);return x;}
	else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}

    以下是实现一颗可以拿去持久化的FHQ Treap的代码:

    const int N(2e5);
int n;ll lastans;
struct node
{
	int rand,size,tag;
	ll val,sum;
	int lson,rson;
}tree[(N<<7)+10];
int rt[N+10];
inline int new_node(long long v=0)
{
	static int tot(0);
	tpi.val=v;tp.sum=v;
	tp.rand=rand();tp.size=1;
	return tot;
}
inline int copy_node(int p)
{
	int ret=new_node();
	tree[ret]=tree[p];
	return ret;
}
inline void push_up(int p)
{
	tree[p].size=tls(p).size+trs(p).size+1;
	tree[p].sum=tls(p).sum+trs(p).sum+t(p).val;
}
inline void push_down(int p)
{
	if(!t(p).tag)return;
	if(ls(p))ls(p)=copy_node(ls(p));
	if(rs(p))rs(p)=copy_node(rs(p));
	swap(ls(p),rs(p));
	if(ls(p))tls(p).tag^=1;
	if(rs(p))trs(p).tag^=1;
	tree[p].tag=0;
}
void split(int p,int k,int &x,int &y)
{
	if(!p){x=y=0;return;}
	push_down(p);
	if(tls(p).size<k){x=copy_node(p);split(rs(x),k-tls(p).size-1,rs(x),y);push_up(x);}
	else{y=copy_node(p);split(ls(y),k,x,ls(y));push_up(y);}
}
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	push_down(x);push_down(y);
	if(t(x).rand<t(y).rand){rs(x)=merge(rs(x),y);push_up(x);return x;}
	else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}

    </Part1.FHQ Treap>

    <Part2.操作实现>

    本题中，我们一共要实现4个操作(单点插入，单点删除，区间反转，区间求和)。
    暂且抛开可持久化不谈，具体实现起来也不难。
    1.插入:
    在第p个数后插入数x,就是把p拆下来然后再使用两遍merge，将它们粘在一起。

    插入操作代码:

    		if(op==1)
		{
			scanf("%lld%lld",&a,&b);
			a^=lastans;b^=lastans;
			split(rt[v],a,x,y);
			rt[++cnt]=merge(merge(x,new_node(b)),y);
		}

    2.删除:
    删掉第p个数，就是将它的两头分别拆下来，再拼接在一起。

    删除操作代码:

            if(op==2)
        {
            scanf("%lld",&a);
            a^=lastans;
            split(rt[v],a,x,z);
            split(x,a-1,x,y);
            rt[++cnt]=merge(x,z);
        }

    3.翻转:
    将区间[l,r]翻转，就是将要反转的区间给拆下来，打上标记，再粘回去。

            if(op==3)
        {
            scanf("%lld%lld",&a,&b);
            a^=lastans;b^=lastans;
            split(rt[v],b,x,z);
            split(x,a-1,x,y);
            t(y).tag^=1;
            rt[++cnt]=merge(merge(x,y),z);
        }

    4.查询: 查询区间[l,r]的最大值，就是将该区间拆下来，输出树根，再粘回去。
    查询操作代码:

            if(op==4)
        {
            scanf("%lld%lld",&a,&b);
            a^=lastans;b^=lastans;
            split(rt[v],b,x,z);
            split(x,a-1,x,y);
            printf("%lld\n",lastans=t(y).sum);
            rt[++cnt]=merge(merge(x,y),z);
        }

    代码贴一下:

    		scanf("%d%d",&v,&op);
		if(op==1)
		{
			scanf("%lld%lld",&a,&b);
			a^=lastans;b^=lastans;
			split(rt[v],a,x,y);
			rt[++cnt]=merge(merge(x,new_node(b)),y);
		}
		if(op==2)
		{
			scanf("%lld",&a);
			a^=lastans;
			split(rt[v],a,x,z);
			split(x,a-1,x,y);
			rt[++cnt]=merge(x,z);
		}
		if(op==3)
		{
			scanf("%lld%lld",&a,&b);
			a^=lastans;b^=lastans;
			split(rt[v],b,x,z);
			split(x,a-1,x,y);
			t(y).tag^=1;
			rt[++cnt]=merge(merge(x,y),z);
		}
		if(op==4)
		{
			scanf("%lld%lld",&a,&b);
			a^=lastans;b^=lastans;
			split(rt[v],b,x,z);
			split(x,a-1,x,y);
			printf("%lld\n",lastans=t(y).sum);
			rt[++cnt]=merge(merge(x,y),z);
		}

    </Part2.操作实现>

    <Part3.可持久化证明>

    为什么FHQ Treap可以依靠可持久化来优化空间复杂度呢?
    其实很简单，就是因为Split过程中可以对点进行复制，并且每次修改的必然只有一个子树上的点。
    而且Split和Merge总是成对出现，我们就只用复制一次。

    </Part3.可持久化证明>

    完整代码:

    #include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<complex>
#include<iostream>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define INF 0x3f3f3f3f
#define ls(p) tree[p].lson
#define rs(p) tree[p].rson
#define tls(p) tree[ls(p)]
#define trs(p) tree[rs(p)]
#define t(p) tree[p]
#define tpi t(++tot)
#define tp t(tot)
using namespace std;
const int N(2e5);
int n;ll lastans;
struct node
{
	int rand,size,tag;
	ll val,sum;
	int lson,rson;
}tree[(N<<7)+10];
int rt[N+10];
inline int new_node(long long v=0)
{
	static int tot(0);
	tpi.val=v;tp.sum=v;
	tp.rand=rand();tp.size=1;
	return tot;
}
inline int copy_node(int p)
{
	int ret=new_node();
	tree[ret]=tree[p];
	return ret;
}
inline void push_up(int p)
{
	tree[p].size=tls(p).size+trs(p).size+1;
	tree[p].sum=tls(p).sum+trs(p).sum+t(p).val;
}
inline void push_down(int p)
{
	if(!t(p).tag)return;
	if(ls(p))ls(p)=copy_node(ls(p));
	if(rs(p))rs(p)=copy_node(rs(p));
	swap(ls(p),rs(p));
	if(ls(p))tls(p).tag^=1;
	if(rs(p))trs(p).tag^=1;
	tree[p].tag=0;
}
void split(int p,int k,int &x,int &y)
{
	if(!p){x=y=0;return;}
	push_down(p);
	if(tls(p).size<k){x=copy_node(p);split(rs(x),k-tls(p).size-1,rs(x),y);push_up(x);}
	else{y=copy_node(p);split(ls(y),k,x,ls(y));push_up(y);}
}
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	push_down(x);push_down(y);
	if(t(x).rand<t(y).rand){rs(x)=merge(rs(x),y);push_up(x);return x;}
	else{ls(y)=merge(x,ls(y));push_up(y);return y;}
}
int main()
{
	srand(224144);scanf("%d",&n);
	int cnt(0);int v,op;ll a,b;int x,y,z;
	while(n--)
	{
		scanf("%d%d",&v,&op);
		if(op==1)
		{
			scanf("%lld%lld",&a,&b);
			a^=lastans;b^=lastans;
			split(rt[v],a,x,y);
			rt[++cnt]=merge(merge(x,new_node(b)),y);
		}
		if(op==2)
		{
			scanf("%lld",&a);
			a^=lastans;
			split(rt[v],a,x,z);
			split(x,a-1,x,y);
			rt[++cnt]=merge(x,z);
		}
		if(op==3)
		{
			scanf("%lld%lld",&a,&b);
			a^=lastans;b^=lastans;
			split(rt[v],b,x,z);
			split(x,a-1,x,y);
			t(y).tag^=1;
			rt[++cnt]=merge(merge(x,y),z);
		}
		if(op==4)
		{
			scanf("%lld%lld",&a,&b);
			a^=lastans;b^=lastans;
			split(rt[v],b,x,z);
			split(x,a-1,x,y);
			printf("%lld\n",lastans=t(y).sum);
			rt[++cnt]=merge(merge(x,y),z);
		}
	}
	return 0;
}

    题解结束

    • 1

    【模板】可持久化文艺平衡树

    信息

    ID
    4067
    时间
    2500ms
    内存
    1024MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 23ms