UOJ Logo EnofTaiPeople的博客

博客

Sone1,从 LCT 到 SATT 的跃进

2023-01-31 08:17:57 By EnofTaiPeople

Part1 前言

P5649 Sone1 是一个神奇的题,用 $25$ 个字概括:

链加链赋值,最值与求和,子树加赋值,最值与求和,换根换父亲。

可以认为是一道解法很多的开放题。


Part2 重工业理论与实现细节

$\text{LCT}$ 的原理是使用 splay 维护实路径,这样可以实现平摊 $O(\log n)$ 实现链修改,链查询。

为了对虚儿子进行维护,我们应当新开一个 splay 维护虚儿子,编号为 $x+n$。

每一个父亲记录其虚儿子 splay 的根节点,注意,只有 isroot(x),$x+n$ 才有意义。

事实上,实路径和虚子树的 splay 可以共用,在实路径 splay 时,需要将原来的根节点从虚子树中删除,再将新的根节点插入,复杂度瓶颈就在此处。

这样来说,如果把虚子树根看作中儿子,这就是三度化的 $\text{SATT}$。

但我还是看不懂 $\text{SATT}$,由于找前驱后继无法平摊,所以时间为 $O(\log^2n)$。

用 $\text{SLT,splay-leafy-tree}$ 来维护虚儿子可以做到 $O(\log_2n)$ 的 access

但这样无法共用 splay,码长要翻一倍,这也称为 $\text{AAAT}$。

重工业还有一个特点,把 tag 看作一次函数,将 dat 打包,省去了 addtagpushdown 的分类讨论,进一步减小码量,当然这个也可以单纯地用矩阵乘法来理解。

具体实现要记录两个标记,表示链上修改和链外(虚子树)修改,还要记录三个数据,表示链上和,链外(虚子树)和,还有自己的值。

贴上评测链接


Part3 从 $\text{AAAT}$ 理论到 $\text{SATT}$

显然,大多数大佬能看懂论文哥的文章

但实现部分我是观察 AC 代码才理解的。

如果你只想学一种动态树而不愿意多做研究,那么只需要能理解 $\text{AAAT}$ 理论,那么你也能看懂 $\text{SATT}$ 的实现过程。

但在读下文前,请先将论文哥的文章先读三遍,可以大致理解一下 $\text{top-cluster}$ 理论。

上图是一棵树,加粗的点表示实儿子,这棵树所对应的 $\text{SATT}$ 如下图:

其中的 $r1,r2$ 表示 $\text{rake node}$,其余表示 $\text{compress node}$。

可以粗略理解为 $\text{compress node}$ 维护实链,$\text{rake node}$ 维护虚儿子。

但这里 $\text{rake node}$ 并没有和上方的 $\text{compress node}$ 失去联系,而成为了$\text{compress node}$ 的中儿子

$\text{compress node}$ 在 pushdown 时需要加给子树的标记会传给中儿子。

$\text{rake node}$ 在 pushdown 时会给子树的两个标记都加上自己的标记。

注意 $\text{rake node}$ 只有一个标记,所以接受标记时也只有一个标记会用到。

可以简单理解成 $\text{rake node}$ 是维护虚子树的 $\text{SLT}$,但如果只有一个虚儿子,唯一的 $\text{rake node}$ 也会只有一个儿子。

任何时刻 $\text{rake node}$ 都不会中儿子

access 时只需要一次全局 pushdown,因为任何一个节点都可以一次经过 $\text{compress node}$ 和 $\text{rake node}$ 到达根簇。

遍历时只需要从根簇出发,遍历左右儿子和中儿子即可。

这样可以整体看作一棵大 splayaccess 时间复杂度为均摊 $O(\log n)$。

由于只需要一次全局 pushdown,只有一棵树,常数相较 $\text{AAAT,LCT-ETT}$ 十分优秀,码量也很小。


Part4 其他做法

上面提到了两种做法是 $O(q\log^2n)$ 的:虚子树 $\text{LCT}$,$\text{LCT-ETT}$。

也有两种是 $O(q\log n)$ 的:$\text{AAAT}$ 和 $\text{SATT}$。

你会发现,它们都是基于 $\text{LCT}$ 的,所以时间复杂度都是均摊的。

假如你想要严格复杂度,甚至可持久化

我们先考虑只要非暴力就行的方法。

注意:以下部分纯口胡,有错误可以直接指出。

  • 每次打通最多增加 $O(\log n)$ 势能,所以可以每 $K$ 次操作重构,注意这里需要重链剖分建全局平衡二叉树。
  • 于是重构复杂度为 $O(\dfrac{qn}K)$。
  • 每次操作最多使用 $O(K\log n)$ 势能。
  • 总复杂度为 $O(qK\log n+\dfrac{qn}K)$。
  • 平衡一下取 $K=\sqrt{n\log n}$,总时间 $O(q\sqrt{n\log n})$。

否则你就不能使用势能了,而需要保证操作结束后保持严格重剖,具体地你需要将轻边抖落,重边连上,同时使用重量平衡树,注意这里使用 treap 做到期望复杂度会相对好写。

当然这个算法是暂时被我认为是考场不可写作的,注意 $\text{LCT}$ 和 $\text{SATT}$ 并不是。


Part5 后记

这道题可以被称作 $\text{Top Tree}$ 的简单应用,事实上静态时的 $\log$ 划分结构也是 $\text{Top Tree}$ 的良好性质,详见此文,于是这道题就真的成为 $\text{Top Tree}$ 的简单应用了。

Top Tree 树上邻域数点

2022-11-24 10:48:37 By EnofTaiPeople

Part1 前言

题意需要我们维护一棵静态树,$\text{rake}$ 和 $\text{compress}$ 都需要通过调用函数实现,查询到节点 $x$ 距离不超过 $d$ 的边集信息,且每次查询只能进行一次信息合并,$n\le2\times10^5,q\le10^6$。

它们是树收缩($\text{tree contraction}$)的两个基本操作,$\text{rake}$ 消除一个度为 1 的点,$\text{compress}$ 消除一个度为 2 的点,此外这些操作会把两条边替换为一条边,收缩过程中,簇的合并结构形成了一个树:


Part2 $\text{Top Tree}$ 维护边集的静态构建

这道题的本质是 $\text{Top Tree}$ 上换根 dp,为了方便转移和查询,我们需要将 $\text{Top Tree}$ $\text{leafy}$ 化,使得每一条边所对应节点都是叶子,然后参照全局平衡二叉树的建立方式,注意节点 $1$ 没有父边,所以要忽略掉。

lucqyjh7.png

上图是一棵树,加粗的点表示重儿子,它所对应的 $\text{leafy-top-tree}$ 如下图:

xkgbvgtw.png

其中 $r1\sim r4$ 表示 $\text{rake-node}$,$c1\sim c3$ 表示 $\text{compress-node}$,容易发现,它是一棵二叉树,有 $2n-3$ 个节点。


Part3 对簇内信息的记录

簇其实就是连通的边集,并且有两个端点,上图的 $\text{Top Tree}$ 中,每一个节点都表示了一个簇。

如何维护簇内信息?

记 $g(x,0/1,k)$ 表示到左右端点距离为 $k$ 以内的边集信息。

对于一个 $\text{rake-node}$,左端点的信息就是两颗子树对应距离 $\text{rake}$ 得到的结果,由于建树时默认重儿子在左子树,所以右端点会继承左子树的右端点,自然也会继承左子树的右端点邻域信息。

对于每一个节点,维护一个 $len$,表示簇的左右端点距离,这样继承之后会将右儿子的 $k-len$ 邻域信息并进来:

ln[x]=ln[ls],U[x]=U[ls],V[x]=V[ls];
for(i=0;i<=rz[x];++i){
    g[x][0][i]=R(G(ls,0,i),G(rs,0,i));
    g[x][1][i]=R(G(ls,1,i),G(rs,0,i-ln[x]));
}

对于一个 $\text{compress-node}$,左端点是左儿子的左端点,右端点是右儿子的右端点,合并时 $len$ 会相加,同样在处理左/右端点信息时取的是右/左儿子的 $k-len$ 邻域信息:

ln[x]=ln[ls]+ln[rs],U[x]=U[ls],V[x]=V[rs];
for(i=0;i<=rz[x];++i){
    g[x][0][i]=C(G(ls,0,i),G(rs,0,i-ln[ls]));
    g[x][1][i]=C(G(ls,1,i-ln[rs]),G(rs,1,i));
}

由于每一个节点只会保留边数的信息,而此树具有全局平衡的性质,所以时空复杂度 $O(n\log_2n)$,这样就可以通过 $u=1$ 和 $n\le2000$ 的测试点了,具体地,可以对于每一个需要的根节点建一棵树,由于根节点必定是根簇的左端点,所以可以直接查询簇内信息,可以得到 $30pts$,时空复杂度 $O(rn\log_2n)$,$r$ 表示查询的不同节点个数。


Part4 对簇外信息的记录

发现对于一个节点,如果不是根簇端点,可能会很尴尬:从叶子往上跳,跳多了得到的信息就超了,跳少了信息又不完全,我们无法做到让查询的信息总在一个簇内与簇的某一端点完全相邻,于是需要记录簇外的信息。

记 $h(x,0/1,k)$ 表示 $x$ 的簇外到左/右节点距离为 $k$ 以内的邻域信息。

无论是哪一个节点,它的簇外信息都有两部分组成:父亲的簇外信息和兄弟的簇内信息,这方面不难推导,依旧只需要对于两种类型的节点分类讨论就可以了:

if(tp[x]){
    h[ls][0].resize(rz[x]+1);
    h[ls][1]=h[rs][0]=h[ls][0];
    h[rs][1]={emptyinfo};
    for(i=0;i<=rz[x];++i)
        h[ls][1][i]=H(x,1,i);
    for(i=0;i<=rz[x];++i){
        h[ls][0][i]=R(G(rs,0,i),H(x,0,i));
        h[rs][0][i]=R(C(G(ls,0,i),H(ls,1,i-ln[ls])),H(x,0,i));
    }
}else{
    h[ls][0].resize(rz[x]+1);
    h[rs][0]=h[ls][1]=h[rs][1]=h[ls][0];
    for(i=0;i<=rz[x];++i){
        h[ls][0][i]=H(x,0,i);
        h[rs][1][i]=H(x,1,i);
        h[ls][1][i]=C(H(x,1,i-ln[rs]),G(rs,0,i));
        h[rs][0][i]=C(H(x,0,i-ln[ls]),G(ls,1,i));
    }
}

大家可能发现了,对于每一个节点的簇外信息,我们都将其保留到了父亲的大小,这样可以方便查询。

具体地,从查询节点开始跳,直到父亲的簇大小超过 $d$ 为止,这样当前的簇内信息必定被完全包含,簇外信息也必定经过了预处理,可以通过两次 $\text{compress}$ 得到答案。

容易发现,这一部分必定会完全包含簇内信息,所以在预处理时将 $h(x,0,k)$ 与 $g(x,0,sz_x)$ 合并,就能保证查询时只需要一次 $\text{compress}$ 了,符合题意要求,时空复杂度 $O(n\log_2n)$。


Part5 代码效率说明

首先,这是我的第一次提交记录,也推荐大家参考,因为没有删注释,但是只有 $97$ 分,因为交完之后,我发现在本地纯随机造树就卡成了 too many MR,MC operations in init(),然后就莫名其妙地 Hack 成功了,后来发现这是被卡常了,微调了一下建树过程,就通过了,或许是出题人并不想卡人?反正目前是最优最短解,指不定哪一天就被人挤下去了。

然而,这样的做法又被我自己 Hack 掉了,原因是,当数据为一棵完全二叉树时,高度会达到 $60$,或许在时间上没有问题,但函数调用次数会大大增加,超过了 $3\times10^7$,所以需要进一步卡常,具体地,在 dp 时不需要处理到边集大小,只需要处理到直径就可以了。


Part6 后记

不知道自己想干什么,学一道题目花了一个星期,或许这是我联赛之前的最后一次任性吧。但这道题真的十分有教育意义,将树上问题在链和子树的基础上,又向全新的“邻域”问题发展,也让我了解到了 $\text{Top Tree}$ 的更多功能。

最大流加强版,从 ID 算法到 LCT

2022-11-15 21:24:02 By EnofTaiPeople

Part1-Improved Dinic

ID(Improved Dinic) 算法是一种求最大流的高效算法,在随机图上复杂度为 $O(km)$,其中 $k$ 是一个较小的常数,一般在 $10$ 左右。缺点也很明显,加边离线,复杂度上限未知(可以理解为上限是 $O(kn^2m)$,但卡到 $O(nm)$ 都不容易做到)。

ID 算法原理就是,对 Dinic 算法进行很多优化,最后不仅代码较短,效率也很高,值得一提的是,即使是小规模数据,他也能跑得比一般算法快。

具体优化如下:

  1. 当前弧(允许弧)优化;
  2. 分段加边优化;
  3. 先正后反(贪心初始流)优化;
  4. gap 优化。

当前弧(允许弧)优化大家都懂,分段加边优化是为了防止边权差异过大,因为 Dinic 算法只有在边权差异大时会跑得较慢。

贪心初始流是采用了二分图增广路算法的贪心初始匹配思想,先不连反边是为了不然反边影响初始效率,gap 优化可以参照 ISAP,AC 记录

Part2-LCT-Dinic

这是一个最坏复杂度为 $O(nm\log n)$ 的最大流算法。

把 ID 卡慢很简单,$k$ 可以被卡到 $\frac n3$ 左右,虽然通过此题的数据范围绰绰有余。

我们需要对 Dinic 的增广过程进行研究,考虑其之所以单次增广最坏为 $O(nm)$ 是因为每一条增广路最多有 $n$ 个点,由于可能每一条路有且仅有一条边满流,所以最多会增广 $m$ 次。

发现一条边在一条增广路上如果没有满流,就还会继续扫到,这样对效率的影响极大,于是可以用数据结构来维护连边,断(零)边,链减(得到的流量),使用可爱的 LCT 十分合适,于是就这样愉快地决定啦!

由于单次增广每一条边最多只会加入一次,减少一次,每一次加入减少的复杂度都是平摊 $O(\log n)$ 的,于是总复杂度为 $O(nm\log n)$。

加上 ID 的优化三(贪心初始流)就可以通过 luogu 数据了,并且速度比 ID 快一倍。

但是,在 UOJ 上会 TLE

Part3-总结

其实 HLPP 的优势局限于本题的数据范围,再稠密点常数没有 MPM 小,再稀疏点就不如 LCT-Dinic。

以上 ID 的代码能通过 Luogu、LOJ、UOJ 的数据,但 LCT-Dinic 即使分段连边也通不过 UOJ 的第三十个测试点,而该点 ID 却能在 $1ms$ 内通过,所以特殊构图能卡 LCT-Dinic,毕竟 LCT 常数大,且每次都有 $\log$,并且分段连边时答案变得飞快,根本没有一条一条 $\log$ 增广的时间。

事实上,我还没见过有人在建模题上卡 Dinic,这就当整活图一乐了。

EnofTaiPeople Avatar