题解：P4246 [SHOI2008] 堵塞的交通

pldzy · 2024-11-10 01:42:37 · 题解

来顺一下思路？

本篇题解的定位和目的是尽笔者所能帮助大家搞清楚题解区“考虑线段树”这句话背后的逻辑和原因。

换句话说，本题解重点在于理清思路线的来历和去向，而不在于解释线段树 pushup() 该怎么维护。

个人建议先去阅读其他题解，在“明白如何做但不知道为什么这么做”的时候阅读本篇题解。

Solution

Part 1

首先，抛开这个线段树的 tag，题目询问连通性，点边量级相同，考虑线段树分治套上可撤销并查集做离线的动态图连通性即可。优点是直接无脑套模板就好。

考虑不用动态图连通性，从这个图的特点出发的做法。最终联通的路径一定是一个蛇形，特殊情况是在首尾两端路径形态可能不同。发现单行的话很好做，但是双行的话最终答案路径的形态可能非常复杂，指会在两行之间交替出现，非常不好维护。

Part 2

考虑这种在类似序列形态的图上“走”的常见套路。通常在一类问题中，我们会考虑用倍增来模拟或者加速我们模拟路径行走的过程。形象地，我们会把可能的行走的路径拆分成若干段，一段一段地跳。即忽略过程，只记录结果，分段解决子问题。

回归到这道题，题目询问的是连通性。维护连通性，除了并查集直接维护之外，我们可以考虑从它的传递性入手。同时，发现题目每一次询问的都是在列数上的一个区间，既然是询问区间，我们可以尝试延用上面倍增的思路。

本质上是把原问题拆分成子问题，回答询问时合并拆分出来的、已经预处理过结果的子问题。优点是可以很好地平衡我们修改和查询的复杂度，前提是答案具有可拆段合并性。这种思想其实很常见，比如分块、树剖优化 dp、倍增等等，还有就是本题的线段树优化。表面上的区别是 长度相同分段、不基于序列形态的分段、以及多种长度的分段。

而这道题也能用这种思维，一是根据连通性的传递性，我们的答案具有可拆分、可合并的特性，二是询问可视为基于序列形态上的，这给我们提供了充分划分子问题解决的条件。

Part 3

言归正传。考虑我们把最后联通 (r1,c1) 和 (r2,c2) 的路径拆成一段一段，那么每一段我们关心的只是它的起点和终点以及它们俩的连通性。同时，根据这一段路径起点终点的列数，我们 似乎 可以把这段路径放入一段列数区间考虑。具体地，对于列数区间 [l,r]，我们只维护它的 左上角、左下角、右上角、右下角 相互之间的连通性。

但这样还是不够。因为我们可能会有从列 l 出发，走到列 k，然后回到列 r，但是 l<r<k 的情况。也即是说，此时我们的路径可能绕到区间 [l,r] 外面，“间接地”把它的两个端点联通起来了。这种情况如何维护？解决方法就是不维护。重新修改定义：对于区间 [l,r]，考虑维护 只走它内部的边 的前提下，它四个角两两之间的连通性。

这样一来，对于上述的特殊情况，我们有两种解决方式：

• 若 [l,r] 的某个端点不是必须要考虑的点（即它不是询问给出的端点），即我们完全不需要关心 这个点 和 其他点（指区间 [l,r] 的四个角）的连通性。那么上述“走到区间之外”的路径就可以用一个更大的区间 [l,k] 来描述。
• 若 [l,r] 的某个端点是必须要考虑的点（即它是询问给出的端点），即 它 和 其他点（指区间 [l,r] 的四个角）的连通性我们必须要关心（此时两个询问点一个列数是 l，一个列数是 r，否则可以用第一条进一步归约到此条件）。那么此时我们不仅要考虑上述维护的[l,r] 四个角的连通性，还要考虑它们通过区间之外的边联通起来的情况。这种情况我们就需要把 [1,l] 和 [r,n] 的维护情况一起考虑进来并分类讨论了。但是这种情况只会出现一次（即回答询问的时候），所以我们的复杂度可以保证。

Part 4

然后考虑怎么维护上面定义的 [l,r] 四个角两两之间的连通性。因为连通性具有传递性，所以这个问题显然可以再一步递归到子问题 [l,mid] 和 [mid+1,r]，显然可以通过它们两各自的答案以及 连接这两段区间的边 的存在性（即是否“疏通”或“拥堵”）合并得到。通过不断这样二分递归到子问题，且合并答案的复杂度是 O(1) 的，我们就可以 O(\log n) 得到一个区间的答案了。同理，修改也是 O(\log n) 的，因为被“波及”到的区间同理也只有 O(\log n) 个。

很显然，这个结构就是线段树的结构。而这个最终的解法也是我们非常熟悉的，用线段树维护、合并带修改的信息。这样，我们就得到了 O(m\log n) 的做法。

Bonus：同理，这道题也能用分块维护。

希望经过上述两千字的分析（如果你看明白我在胡什么？），你不会再对题解区“考虑线段树”感到莫名其妙和没有头绪了。

Code

被误导了调了好久……

其实没有什么可说的，合并的地方自己画画图搞清楚细节就可以了，回答查询的时候分类讨论一下即可。

注释就不加了，用 0 表示区间左上角，1 表示区间左下角，2 表示区间右上角，3 表示区间右下角。有需要的可以参考一下代码。