[NFLS 1451/4] 大庆 题解

大意

给定一个 $n \times m$ 的方格, 每格中有一个数字, 设两个方格是 联通的 , 仅当两个方格相邻且数字相同 .

$q$ 个询问, 每次给定 $l$, $r$, 求从第 $l$ 列至第 $r$ 列中联通块的个数 .

数据范围

#	%	$n$	$m$	$q$
1	$15$ %	$\le 2$	$\le 10^6$	$\le 1.3 \times 10^6$
2	$75$ %	$\le 10$	$\le 10^5$	$\le 10^5$
3	$10$ %	$= 1000$	$\le 100$	$\le 10^6$

题解

这道题要分成 3 个部分, 对应上表中的三个数据范围.

#1

$n \le 2, m \le 10^6, q \le 1.3 \times 10^6$

可以发现, $n \le 2$, 同时 $m, q$ 很大, 考虑用前缀和解决.

设 $s_i$ 为前 i 列的联通块个数.

$n = 1$ 时:

$$s_i = s_{i-1} + [a_i \not= a_{i - 1}]$$

$n = 2$ 时:

$$s_i = s_{i-1} + [a_{1, i} \not= a_{1, i-1}] + [a_{2, i} \not= a_{2, i-1}] - [a_{1, i} = a_{2, i} \wedge a_{1, i} \not= a_{1, i-1} \wedge a_{2, i} \not= a_{2, i-1}]$$

查询时, 同样解决.

$n = 1$ 时:

$$s_r - s_{l-1} + [a_l \not= a_{l - 1}]$$

$n = 2$ 时:

$$s_r - s_{l-1} + [a_{1, l} = a_{1, l-1}] + [a_{2, l} = a_{2, l-1}] - [a_{1, l} = a_{1, l-1} \wedge a_{2, l} = a_{2, l-1} \wedge a_{1, l} = a_{2, l}]$$

#2

线段树.

设 $id(i, j) = (i - 1) \cdot m + j$

每个节点存储 $l, r, cnt$, 分别代表该区间左端和右端的编号 (编号相同就代表数字相同, 反之不一定) , 和联通块个数.

先考虑每一列:

$$l_{i, j} = l_{i - 1, j}, i \ge 2 \wedge a_{i, j} = a{i - 1, j} \newline \newline l_{i, j} = id(i, j), otherwise$$

然后考虑合并

首先 $cnt \leftarrow cnt(ls) + cnt(rs)$.

对于中间的两列, 即 ls.r 和 rs.l, 若相同, 则用 dsu 加入同一个集合, 并 $cnt \leftarrow cnt-1$.

然后对于左右两列, $l \leftarrow l(ls)$, $r \leftarrow r(rs)$, 并要在 dsu 中查询.

合并完将 dsu 恢复.

#3

仿照 #2 的情况, 独立处理每一列, 然后合并时, 若两侧相同且不在同一个集合内, 就合并, $cnt \leftarrow cnt - 1$.