告诫后人

CF576E Painting Edges

ducati @ 2023-06-26 09:34:13

  1. 请注意你的空间消耗。在我的第一发提交里，我将用于撤销的栈开到了 32n 级别，事实上只要开到 3n 就足够了，因为线段树上每条直链包含的询问两两不同，而每次合并只会修改三个位置的值（祖先、父边及连通块大小）。

2. 可撤销并查集，不要路径压缩！！！

  • I. 字面意思：不要在跳祖先的时候，把连向祖先的边给改了。

  • II. 不要在跳祖先的时候，把父边边权给改了。换言之，别在跳祖先的时候，把边权给路径压缩了，不然存储的边权是个啥玩意？

  1. 我们可能会计算出两个点到根路径上的边权和。为按秩合并需要，我们可能会在随后的合并中交换这两个点的编号，别忘了把存储的边权和也交换一下。

  2. 请保证每个询问在线段树上插入的区间非空，否则可能导致死循环。

by ducati @ 2023-06-26 09:35:13

MLE 1 发，WA 7 发，上面是我犯的错误去重后的结果。

by chenxia25 @ 2023-06-26 09:48:08

/wx

by UnyieldingTrilobite @ 2023-06-26 09:51:16

请注意你的空间消耗

这就是为什么我一直用 std::stack。

by syzf2222 @ 2023-06-26 10:33:48

当时我写这个题的时候才发现原来我的可撤销并查集一直都写的是个错的/tx

by TernaryTree @ 2023-06-26 10:39:57

典

by Nine_Suns @ 2023-07-17 20:14:13

MLE 了 6 发

再也不手写 stack 了

|