文章目录

洛谷 P4121 WC2005 双面棋盘 做题笔记

发布于

题意

给出一个 $n \times n$ 的黑白棋盘。你要处理 $m$ 次修改,每次修改给出一个点 $\left(x, y\right)$,表示你要把 $\left(x, y\right)$ 的颜色反转。每次修改后输出有多少个白色连通块和有多少个黑色连通块(四联通)。

$1 \leq n \leq 200, 1 \leq m \leq 10^4$

题解

线段树套并查集。

开一颗线段树,线段树上每个节点维护一个并查集。并查集维护每一行的联通情况。

每次修改时,暴力重构该行的并查集。

线段树上合并:枚举每一列,看左儿子的最后一行上该列的颜色 跟 右儿子的最后一行上该列的颜色 是否相同。相同就把他们合并。

时间复杂度 $\mathcal O\left(m\left(n \log^2 n\right)\right)$


暂无评论

发表评论