UOJ Logo zx2003的博客

博客

Weight Balanced Top Tree

2022-08-19 17:22:20 By zx2003

一直觉得自己写作水平比较烂,而且现在也比较懒,大家凑活着看吧


前置知识:Top Tree相关理论

什么是Weight Balanced Top Tree?

就是满足重量平衡性质的Top Tree。

重量平衡的原始定义是,对于任意节点 $u$,其任意孩子节点 $v$,满足 $v$ 的子树大小 $size(v)$ 与 $u$ 的子树大小 $size(u)$ 的比值在常数范围内。

由于严格的重量平衡性质比较难以满足,这里将条件稍微放宽为,每个Top Tree中的节点向上走 $O(1)$ 后,所在节点的子树大小能翻常数倍。后面在一些问题上可以看到这个性质的用处。

静态树上的做法

可以发现流行的全局平衡二叉树就满足重量平衡的性质。

动态树上的做法:期望复杂度

每个点赋个随机权值,一个点的重儿子是子树max最大的那个儿子。

然后再对重链建treap,轻儿子也要用treap按乱序维护。

实链上的分裂合并就是treap的分裂合并,偏好儿子的切换就按子树max的来维护。

link/cut时需要一些额外讨论。

可以证明每个点期望深度为 $O(\log{n})$。

严格来说treap实现的版本不能算重量平衡树,但是在后续一些场景的分析中,表现跟严格复杂度的版本差不多。

一份参考实现

动态树上的做法:严格复杂度

子问题:带权重量平衡树

使用平衡树维护带权序列,支持两种操作:

  • merge(L,x,R),x是单点。

  • split(A,k),表示将树A从位置k处分开。返回三元组(L,x,R),x是单点,L,R是相应前后缀组成的平衡树。

希望的复杂度:$O(\log\frac{|L|+w(x)+|R|}{w(x)})$ 复杂度维护平衡树的结构,其中 $w(x)$ 是节点 $x$ 的权重,$|L|,|R|$ 是 $L,R$ 的子树大小

维护不变量:

一个大小k的叶子必须在第i层,满足 $2^i<=k<2^{i+2}$。

任意一个第i层的块都要满足size严格小于 $2^{i+2}$。

第i层维护的块序列中,非叶的部分可以由第 $i-1$ 层中连续几个块(可以是一个)合并得到。第i层维护的块中,相邻两个块不能都小于 $2^i$。

可以验证,全树是重量平衡的(每个点往上走 $O(1)$ 步后size就会翻至少 $O(1)$ 倍),进而有两个推论:1.全树深度为 $O(\log{n})$; 2. x的深度为 $O(\log{\frac{n}{w(x)}})$

记一个块的秩为其所在的层,注意一个块所在的层是一个连续区间(因为允许父节点只有一个孩子,可以压起来),所以其秩也是一个连续区间,实现中可以仅存储其左右端点,而无需对每一层新建一个仅有一个儿子的节点。

shrink

传入参数为两个栈和一个中间元素,$st1,st2,a$

两个栈的栈中元素均满足秩从栈顶往下单调递增,并且 $a$ 的秩不超过两个栈的栈顶元素

可以想象a是秩的最低谷,两个栈是从谷底往两侧延伸的山丘,然后我们要从a开始一点一点把中间的坑填平,将栈中节点与 $a$ 一起合并为一棵合法的树。左右两侧的栈中元素需要满足一定的性质来保证能填平。

首先将 $a$ 的秩区间 $[r1,r2]$ 变成 $[r1,r1]$,避免 $a$ 的秩虚高

每次对于谷底所在的层i,要把连续的若干个秩为i的元素合并成秩为i+1的元素,执行如下贪心策略:

  • 如果 $\frac{元素size和}{2^i}<8$,直接合并
  • 如果按中位线分开可以分成2半且保证size不超限,按中位线均匀分
  • 则先从左到右和从右到左各贪心地切尽量长的一刀,中间剩下的部分再直接贪心切
expand

传入一个栈s,栈中元素均为树中节点。返回另一个栈s',为将s的栈顶元素u弹掉后再将u的所有儿子按顺序加入栈

merge

将L入栈s。不断对执行 $s \leftarrow expand(s)$,直到s栈顶元素变成叶子或者栈顶元素的秩小于等于 $a$ 的秩。

对R同样操作,然后调用shrink。

split

先将树split成一个单点和两条链。直接将链入栈不可取,需要仿照merge中过程将链中元素给适当展开。

然后将左链和右链的链底的子树截下来,再调用shrink即可。

正确性

shrink过程中唯一可能违反性质的就是,某一轮填平谷底后新元素的size太小,并且此时栈顶元素(也就是未来第i层中的左右邻居)size也太小。

如果此时谷底元素已经有栈中元素参与合成了,由于栈中元素的size原本是满足条件的(是从合法的树中截出来的链),所以此时谷底元素的size一定也合法。

否则如果谷底元素size仍不合法,则在调用shrink前的过程中,栈顶元素一定会被不断expand直到合法。

完整版

用带权重量平衡树作为实链的数据结构,链剖策略使用严格重剖。注意轻子树也使用WCWBT来维护最重的儿子。

access

将一个点到根的链强制变为实链

drop

将实链上的轻边都抖落下去

注意access和drop为都需要注意轻重边切换的顺序,反了的话复杂度是错的;可以使用一个vector存储要切换的边最后再按正确顺序处理。

link/cut时需要一些额外讨论,细节这里略。

最后单次动态树操作的复杂度为严格 $O(\log{n})$,树结构上的静态查询跟普通Top Tree一样做即可。

一份参考代码实现

WBTT能干什么

首先普通Top Tree能干的WBTT基本都能干

其次是一些特殊性质的问题

树分块类的问题

问题形式大概类似于 CTS2022 WBTT

用WBTT维护树结构,对于size小于 $B$ 的子树用 $O(size)$ 的代价维护信息;查询时递归到查询区间中所有size不超过 $B$ 的子树上即可。

重量平衡的性质保证了修改的复杂度,也保证了查询时只会递归到 $O(\frac{n}{B}+\log{n})$ 个子树上,单次复杂度 $O(\sqrt{n})$

以及实际上我们还可以比这题中做得更强,由于Top Tree还给出了块间分治结构,我们在上面跑fractional cascading的话,就可以单次 $O(\sqrt{n})$ 的复杂度解决区间rank上树的问题。

关于treap版本的复杂度分析,

一个引理是,如果树的大小<=B,则从单点 $i$ 往上合并信息的期望代价 $O(B)$。考虑 $j\gt i$ 对 $i$ 的贡献,期望是 $j$ 这个后缀出现的单调栈长度,等于 $H_{n-i+1}-H_{j-i+1}$,其中 $H_i$ 表示调和级数第 $i$项。对求和式稍微放缩一下,可以得到这是 $O(树的大小)$。

完整的分析细节比较冗长,这里略。

小修改动态树上的情形

大概类似于 wcriq 上树的版本,每次修改操作是从树中间裂出一个节点,要求保证单次最坏复杂度并且维护信息。

把wcriq里的做法改改也能上树,细节略。

浅谈双极定向及其应用

2021-08-09 21:29:36 By zx2003

在洛谷博客的同步

wiki链接

双极定向是说,给定一张无向图,要求给每一条边确定一个方向,使得原无向图成为一个DAG,并且恰有一个入度为0的点 $S$ 和一个出度为0的点 $T$。wiki中似乎将这样的 $S$/$T$ 称呼为 source/sink。

显然不是所有图都有合法的双极定向。

例题——CC CUREK

原题链接

题目大意

给你一张 $n$ 个点 $m$ 条边的无向连通图,保证不存在重边和自环。

这张图的每个点都是白色的,你想要把它们全都染成黑色。刚开始你可以选择一些点把它们染成黑色,并需要付出这些点权值之和的代价;接下来你每次可以选择一个和黑点相邻的白点,并把它染成黑色。你还需要保证在每一步操作(包括最开始染那些点)之后,所有白点的导出子图连通。

请你最小化你所需要付出的代价,并构造一组代价最小时的方案。

做法

算法1

考虑树上怎么做。

首先,最多只能剩一个叶子在最开始没选,否则在染到另一个叶子的父亲时白点会不连通。

我们把点权最大的那个叶子提根,剩下每个叶子都必须在最开始被选。构方案只需要不断剥叶子即可,可以保证始终连通。

算法2

我们从树上的做法得到启发,猜想对原图建出点双树后,只有一个叶子点双最开始没有被选,同时这个叶子是所有叶子中最小权值最大的。

引理1

对于一组初始黑点的方案,满足所有白点初始均连通。则该初始方案合法,当且仅当所有白点构成的点双树上,至多只有一个叶子点双,使得其中的白点不与任何黑点相连通。

引理的必要性是显然的,跟树的情况类似证明即可。对于充分性,我们尝试对白点数量归纳并构造证明。

跟树的情况一样,我们仍然将不与所有黑点相邻的叶子点双提根,之后不断剥剩下的叶子。这样我们唯一需要实现的问题是,在一个点双内给定最开始被染黑的点(只有一个)、需要在最后一个才被染黑的点,求一组合法方案使得它满足题目中所描述的条件。

对于这个问题,每一步如果某个点染黑之后白点仍然连通,这一步就选择染黑该点。证明是简单的,我们考虑新黑点所属的点双,在该点染黑后,原点双分裂成的子点双一定摆成一条链。于是唯一可能新产生的叶子点双,必为链的两端,与新黑点相邻。这样就递归到了白点更少的子问题。

从而引理得证。

直接模拟上述做法,对于每一轮,我们跑出白点导出子图中所有的割点,那么割点就是不能剥的,非割点就是能剥的。复杂度 $O(n^2)$。

算法3

尝试直接优化算法2,发现我们实际上要操作的是删边维护割点。使用维护动态图双连通性的相关算法即可。

复杂度 $o(n^2)$。

算法4

根据前述分析,我们只需考虑原图是点双连通分量的情况,不过这时相对于原问题,会要求染黑的第一个点 $S$ 和最后一个点 $T$ 均固定。

我们尝试递归求解这个问题,但在这之前我们先思考一下有哪些递归手段。

记原图为 $G$。

  • 如果 $G'$ 为 $G$ 删掉一条边得到的图,则 $G'$ 的合法删点顺序对 $G$ 也是合法的。

  • 对于一个二度点 $x$,记其邻居为 $y,z$。对于任意 $G'$ 的合法删点序列 $a$,由对称性不妨设 $y$ 在 $a$中比 $z$ 更靠前,则我们在 $a$ 中 $y$ 的位置后面插入 $x$,即可将 $a$ 改进为图 $G$ 的解。

实际上只靠删边和缩二度点这两种递归手段,足以处理任意点双连通图。

具体的,我们先找出整张图的一棵生成树,然后对于每个叶子,我们保留它最浅的一条返祖边,注意这不改变点双连通性。

这样,每个叶子就都变成了二度点,我们就可以删除所有叶子啦!

如此不断操作下去,整张图就可以变为一条以 $S$ 和 $T$ 为两端点的链。此时合法删点序列的求解是平凡的,还原为原图的解序列也是容易的。

最后总复杂度$O(n)$。

应该说这里的构造过程跟 Ear_decomposition 有点像。

实际上到这里我们已经将双极定向的存在条件以及线性构造方法分析清楚了。下面是一些其它相关题目。

相关题目1——CF1192F

题目链接

可以发现本题题目描述跟上一道题很像,不过细节上有些差异,诸如在两条约束中一个形式是八连通,另一个是四连通;还有多了字典序的要求。

这题和上一题有什么相关性?

先考虑从后往前逐位构造合法解,仿照上一题,我们直接猜想,每一步任选一个与无穷远处四连通的,且删掉后剩下点集仍然八连通的点,都是合法的。

实际上这个命题是对的。只是由于一些不对称性,证明的时候需要不同的处理。

首先将命题形式改造为任一八连通图点集都存在这样的点,并且有 $min(2,点集大小)$ 个合法点。之后我们对点集大小进行归纳。取所有点中最左下方点 $u$,如果这是一个割点,则去掉该点后全集恰划分为两八连通点集 $A,B$,并且 $A,B$ 一定不会出现一个把另一个包在内部的情况——因为 $u$ 向右上方至多连出去四条边。于是由归纳假设,$A \cup \{u\}$ 和 $B \cup \{u\}$ 一定分别包含一个不等于 $u$ 的合法点,且其也是原点集的合法点。对于最右上方的点 $v$ 施以同样处理。如果 $u,v$ 均非割点,则 $u,v$ 已构成两合法点。从而命题得证。

平凡讨论有点多,您也可以选择跳过或者看官方sol。

后续做法

回到原题,问题核心变为如何即时维护所有非割点集合。关于字典序的要求是简单的,只需将存储合法点的容器换成优先队列即可。

注意到八连通意义下的割点是个局部的性质(“so the information about articulation-ness of cells is local”)

于是修改时我们只需对周围 $O(1)$ 个点,检查其各自邻居的连通情况即可

稍微提一下细节,首先八连通的对偶是四连通,然后只需考虑上下左右四个点中同属于一个连通块的白点。

可以发现最后产生影响的一定是白点对(而不是三元组)。

然后只需考虑被检查的点删除后,配合枚举的白点对,能否产生一组割即可。您可以自行手画一下来加以理解。

具体实现的时候,需要维护两个白点是否属于同一个白四连通块。

最开始先跑一遍floodfill标记每个白点所属连通块的颜色,需要手动添加一些辅助白点。

由于修改操作只有黑变白,所以每次从新增的白点开始,暴力标记新产生的与无穷远处连通的白点即可。

相关题目2——IOI2019景点划分

题目链接

首先令 $a \le b \le c$,我们只需求出两连通点集 $A,B$ 使得 $|A|=a,|B|=b$。

考虑对原图建立圆方树,圆点表示割点,方点代表点双。圆点的权重设为1,方点的权重设为点双中的非割点数量。

显然至多只有一个点双 $C$,满足 $A \cap C$ 与 $B \cap C$ 均不为空,否则连接两点双的路径上的割点会导出矛盾。

我们枚举这个点双 $C$ 在圆方树上的方点 $u$。

将 $u$ 提根,如果 $u$ 最大的一个子树大于 $n-a$ 了,则从 $C$ 必然无法导出合法解。

否则,如果 $u$ 最大的子树大于等于 $b$,则在该子树内部任选 $b$ 个点,外部任选 $a$ 个,即得合法解。

最后一种情况,我们需要将点双 $C$ 进行拆分。考虑利用CUREK一题中的构造,我们可以得到 $C$ 中点的一个排列 $p$,使得其所有前缀与所有后缀均构成连通点集。

设 $C$ 中一个割点的权为其在圆方树上的子树大小(以 $u$ 为根),一个非割点的权为1。我们截取 $p$ 的第一个权和不小于 $a$ 的前缀,则该前缀的权和一定不超过 $a+b$——因为最大子树不超过 $b$。于是对应后缀的权和一定不小于 $b$,否则 $a+b+b \gt n$ 矛盾了。可以发现这样的前后缀切分方案导出了一组合法的原图点集划分方案。

并且这样枚举 $C$ 显然是充要的,最后总复杂度为 $O(n)$。

这是一份参考代码,一些实现细节和文中叙述有差异。

感觉在有CUREK一题作为模板的情况下思维量比官方做法小好多,不过得现写CUREK的话就有点大力飞砖了,这玩意还是有点难写的。

关于 UOJ NOI Round #5 Day2T2 一题的其它做法

2021-07-19 22:15:40 By zx2003

这里介绍一个相对通用的办法。

使用重量平衡树(能够保证每个点子树size与自身size只比严格介于 $(c,1-c)$之间的平衡树,$c$ 为取定的常数 )维护序列非0位置。

操作2,3和操作1的区间定位没有影响。

操作1递归访问到的总节点数也不变,唯一问题是信息合并的复杂度。而这满足递归式 $T(n)=T(c*n)+T((1-c)*n)+\log{n}=O(区间长度)$。注意及时清除区间中的0元素。

于是总复杂度仍为 $O(n\log{U}+q\log^2{n})$。

并且我们现在能支持更多操作,比如单点修改权重,对复杂度的影响只有操作1中访问的节点数,均摊代价 $O(\log{U})$;比如序列分裂合并,单次代价与区间定位相同为 $O(\log^2{n})$。

关于重量平衡树,一个OI可写的实现是一种称为 WBLT 的东西。

请问能否开放uoj357的hack?

2020-06-23 18:41:39 By zx2003

我发现对于一些数据,很多ac程序的输出是不等的.

UOJ#446 交互库有锅

2020-01-27 20:54:47 By zx2003
zx2003 Avatar