题解 P5055 【【模板】可持久化文艺平衡树】
题解 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;
}