题意
给出一个 $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)$