P15583 [KTSC 2026] 通信网络 2 / Communication Network 2 题解

Gold14526 · 2026-03-09 08:43:51 · 题解

感觉不是很写的动，先来写个题解吧。

这个题还是挺厉害的。

首先把题目中的每个时间异或上一个边集的形式变为一条边在一段时间出现的形式。

那么这是一个离线类动态图连通性问题，考虑线段树分治。

但是我们还要考虑如何刻画一个点 y 在 [l,r] 这段时间内始终与 x 连通。很难想到，设 f_{i,j} 为第 i 个点在第 j 个时刻时所在并查集集合的根，若 f_x 的第 l\sim r 个数与 f_y 的第 l\sim r 个数相同，那么它们就始终在同一个连通块里，为了方便说明，接下来设 f_i[l\dots r] 表示 f_i 的第 l\sim r 个数组成的子串。

发现 f 的信息量是 O(nm) 的，太大了，不好直接入手，先考虑线段树分治。

考虑类似单 \log 离线动态图连通性的性质，若一个线段树节点 [l,r] 上的边集为 E，那么它子树中将只有 |E| 个 f_i[l\dots r] 不同的点。考虑将异或上一个边集改成先依次加入边集中所有需加入的边再删去需删去的边，使得每条边出现区间的端点两两不同，并对应的修改查询的 l,r 的值，这样分治区间里不同的点就只有 O(r-l) 个。

像 SA 一样，我们维护这些点的 f_i[l\dots r] 的字典序，以及字典序相邻的串的 \operatorname{lcp}，同时维护它们反串的字典序和 \operatorname{lcp}。

考虑在分治的时候解决经过中点 mid 的询问，此时只要 f_x[l\dots mid]=f_y[l\dots mid] 以及 f_x[mid+1\dots r]=f_y[mid+1\dots r]，满足这两个条件要求的点 y 分别是左侧反串字典序上的一个区间和右侧字典序上的一个区间，只需先二分出这两个区间，然后做二维数点即可。