@Venous
2018-05-15T21:44:19.000000Z
字数 3730
阅读 993
知识体系
知识版权所有,未经允许请勿转载哦!
首先明白这个神奇的动态树支持的操作(貌似这个顺序不对)
常见问题形势——
维护两点的连通
维护两点路径权值的和,最大值,最小值,自定义运算值……
维护LCA,直径,重心,自定义点与点的关系……
烦人的动态操作——
连接两个点(先前是不连通的)
把某个点变成某个点的父亲(先前是不连通的)
断开两个点的连接(先前是联通的)
修改点权,边权等等……
它已为关键字(这是很致命的操作)
首先是用维护原树上链的信息,在同一条链上的用连接,不同的用虚边连接这是一个很蛋疼的性质,因而会出现如下一些情况
x是y的父亲,也就是fa[y]=x,但是x并没有y这个儿子,也就是并没有tr[x].ch[0]=y或是tr[x].ch[1]=y
在Splay时可能会将虚边修改为实边
然后还有虚边是怎么连的呢?
称有两棵Splay树A,B,其中B树的根节点是x,x在原树中的父亲是y且y处于A树中,那么则将x向y连一条虚边,我们称为“将辅助树中的根节点连一条虚边指向它在原树中得父亲”
给大家举一个栗子(已"1"为根)
1-2,2-4,2-5,3-6,3-7
那么在LCT中它们则是这么连的(手玩一下大概就懂了)
2-4,2-1,6-3(实边)
2-5,1-6,3-7(虚边)
然后考虑具体模板和操作
这是你中写的
void Rotate(int x)
{
int y=tr[x].fa;
int z=tr[y].fa;
int k=tr[y].ch[1]==x;
tr[z].ch[tr[z].ch[1]==y]=x; tr[x].fa=z;
tr[y].ch[k]=tr[x].ch[k^1]; tr[tr[x].ch[k^1]].fa=y;
tr[x].ch[k^1]=y; tr[y].fa=x;
}
这是你中写的
void Rotate(int x)
{
int y=tr[x].fa;
int z=tr[y].fa;
int k=tr[y].ch[1]==x;
if(!Isroot(y))tr[z].ch[tr[z].ch[1]==y]=x; tr[x].fa=z;
tr[y].ch[k]=tr[x].ch[k^1]; tr[tr[x].ch[k^1]].fa=y;
tr[x].ch[k^1]=y; tr[y].fa=x;
}
所以,用事实说话,其实唯一差距就是加入一句if(!Isroot(y))
的判断,也就是如果y是所处中根的话,就不能将z的儿子修改为x,为什么呢?
在之前介绍优(dan)良(teng)性质的时候就介绍了z并不一定有y这个儿子
这是你中写的
while(tr[x].fa!=goal)
{
int y=tr[x].fa,z=tr[y].fa;
if(z!=goal)
(tr[z].ch[0]==y)^(tr[y].ch[0]==x)?Rotate(x):Rotate(y);
Rotate(x);
}
if(!goal)root=x;
这是你中写的
//Part 1
zhan[++top]=x;
for(int p=x;!Isroot(p);p=tr[p].fa)
zhan[++top]=tr[p].fa;
while(top)Pushdown(zhan[top--]);
//Part 2
while(!Isroot(x))
{
int y=tr[x].fa,z=tr[y].fa;
if(!Isroot(y))
(tr[y].ch[0]==x)^(tr[z].ch[0]==y)?Rotate(x):Rotate(y);
Rotate(x);
}
咱们首先看Part 2,中说的是z!=goal
也就是z不是根的父亲,中是!Isroot(y)
也就是y并不是根,所以本质上一样的
然后Part 1存在的意义是用来翻转标记,由于标记需要从上往下,这在之后的会提到
return tr[tr[x].fa].ch[0]!=x&&tr[tr[x].fa].ch[1]!=x;
如果x的父亲的两个儿子都不是x的话,就说明x的父亲并没有这个儿子,也就说明x是所处Splay中的根(优良性质)
for(int y=0;x;y=x,x=tr[x].fa)
{
Splay(x);
tr[x].ch[1]=y;
Pushup(x);
}
这一部分是把x到原树上的跟节点的路径抠到同一棵中,其余原本的点则断掉,然后具体原理是怎么抠的呢?
具体先把当前的x旋转到该棵Splay中,然后把x的右儿子置为x的假儿子(就是由于优良性质导致的x是y的父亲,但是x并没有y这个儿子),注意原本的x和y是用虚边连接的!
void Makeroot(int x)
{
Access(x);
Splay(x);
Reverse(x);
}
这一部分是把x点放到原树的根节点上去,所以不难想到就是++,由于这一部分是更改了树的根节点,也就是树的结构的,所以一定要记得
int Findroot(int x)
{
Access(x);
Splay(x);
while(tr[x].ch[0])x=tr[x].ch[0];
return x;
}
这一部分是找到x所在的联通块中的根(能维护连通性),但是这一部分并没有改变树的结构!所以千万不需要,然后要找到原联通块的根,就只需要一直跳左儿子就可以了。
因为己经保证Splay已经保证以深度为关键字,所以深度最小的那个点,就是联通块的根节点,至于Findroot后的LCT树只是将树形变了一下!原树的结构是没有改变的!
void Split(int x,int y)
{
Makeroot(x);
Access(y);
Splay(y);
}
这一部分是将LCT树中的x到y的路径给抠出来。所以不难想到是++(这个自己yy一下就好了)
void Link(int x,int y)
{
Makeroot(x);
if(Findroot(y)!=x)tr[x].fa=y;
}
这一部分就是动态维护树的结构了,在两点之间连边。自己yy一下,不难想到是+if(Findroot(y)!=x)
,所以如果条件满足的话,就连边就好了!
但是这也是最容易出错的,因为if(Findroot(x)!=Findroot(y))
是不够好的
void Cut(int x,int y)
{
Makeroot(x);
if(Findroot(y)!=x||tr[x].ch[1]||tr[x].fa!=y)return;
tr[y].ch[0]=tr[x].fa=0;
Pushup(y);
}
这就不用说了吧,将x与y之间的连边断掉(一定要两点在原树中直接有一条边相连)
具体细节也超多的!
Update:5.15
翻转标记(Reverse)
void Reverse(int x)
{
swap(tr[x].ch[0],tr[x].ch[1]);
tr[x].rev^=1;
}
下放标记(Pushdown)
void Pushdown(int x)
{
if(tr[x].rev)
{
if(tr[x].ch[0])
Reverse(tr[x].ch[0]);
if(tr[x].ch[1])
Reverse(tr[x].ch[1]);
tr[x].rev=0;
}
}
然后放一个---[国家集训队]Tree II
这是我有史一以来打过的最长的下放
void pushdown(int x)
{
if(tr[x].mul!=1)
{
ll t=tr[x].mul;
tr[x].v=tr[x].v*t%mod;
if(ls)
tr[ls].sum=tr[ls].sum*t%mod,
tr[ls].add=tr[ls].add*t%mod,
tr[ls].mul=tr[ls].mul*t%mod;
if(rs)
tr[rs].sum=tr[rs].sum*t%mod,
tr[rs].add=tr[rs].add*t%mod,
tr[rs].mul=tr[rs].mul*t%mod;
tr[x].mul=1;
}
if(tr[x].add)
{
ll t=tr[x].add;
tr[x].v=(tr[x].v+t)%mod;
if(ls)
tr[ls].sum=(tr[ls].sum+t*tr[ls].sz%mod)%mod,
tr[ls].add=(tr[ls].add+t)%mod;
if(rs)
tr[rs].sum=(tr[rs].sum+t*tr[rs].sz%mod)%mod,
tr[rs].add=(tr[rs].add+t)%mod;
tr[x].add=0;
}
if(tr[x].rev)
{
if(ls)
Reverse(ls);
if(rs)
Reverse(rs);
tr[x].rev=0;
}
}
然后至于能维护子树信息的骚操作,就留个坑以后再补吧!