题解：CF811E Vladik and Entertaining Flags

· · 题解

每种颜色互相独立，对其分开讨论。将每一列的极长同颜色段当作一个点，然后相邻行将同颜色且有边相邻的点对建一个边（如下图）。

发现有以下性质：

  1. 如果原图是一个森林，那么可以直接用区间内点数减边数来得到连通块数。这启发我们考虑如何扩展到非树边。
  2. 所有边都是 i 和 i+1 之间的边。
  3. 所有的边没有交叉。（2，3 性质启发我们对边进行分类讨论计算贡献。）

朴素做法，我们可以将每个询问的这一矩形拿出来，然后建生成树，然后用上面这个式子得到贡献。

考虑先求出一棵总体的生成树 A。考虑将这棵生成树向上连边。具体地：对于每一个点，贪心地向左边一列，从上至下向相邻同颜色点连边。

然后对于每个区间，先将 A 树树边作为区间生成树树边，然后在区间内对没选的边继续执行上述算法，得到某个区间的生成树 B。

称不在 A 树出现的边为非树边。对于一条从 r-1 列与 r 列的非树边，考虑某个 l，什么时候区间 [l,r] 会算到这条边的贡献。

发现一定存在一个分界点 p，使得 l\le p 时不算这条边的贡献，l>p 时算到这条边的贡献。 仔细分析可以得到，我们其实是需要找到一个时刻，使得这条边两个端点 u,v 恰好不用通过这条边连通。这是对应这条边靠左上的最小环的左端点。

原图可能长这样：（黑色圆形表示一类颜色相同的点）

考虑这样一个图。其中实边为树边，虚边为非树边，其上面标注了点对 (a,b)，(b,c)，(d,e)，(f,g) 非树边的最小环。记最小环左端点为 l，右端点即树边位置为 r，那么对于所有 x>l 且 y\ge r 的区间 [x,y]，该非树边都有 1 的贡献。

树边的贡献是简单的，对于一条从 i-1 列与 i 列的非树边，对所有 x\le i-1 且 y\ge i 的区间 [x,y] 都有 1 的贡献。

求最小环，直接暴力向左边搜索，直到 u,v 在某个位置相连通。复杂度可以均摊，考虑对于一个环最多会延伸到哪里：上边界最极限会贴合着之前的环的下边界，左边界最极限会贴合这之前的环的右边界。所以总势能是网格大小是 O(nm)。

我们每次扩展长度为 p，最极限是用 O(p) 的势能，然后用 O(np) 的复杂度搜索。这一部分的复杂度为 O(n^2m)。

计算贡献用二维数点。最后用点数量减边数量即可。所以总时间复杂度为 O(n^2m+nm\log m)。

同时这个方法可以直接计算所有区间连通块数之和以及最大区间连通块数。

代码。