题解

思路

把每个颜色独立考虑。由于操作颜色整体单调不降，一个格子持有某个颜色的时间至多形成一个连续区间。某一时刻的总连通块数，等于各颜色诱导子图的连通块数之和。

对非零颜色 $c$，所有变成 $c$ 的时刻集中在同一个连续操作段内；该段结束后只会有格子离开 $c$，不会再有格子进入。因此，进入阶段可正向加点，离开阶段可倒序加点。颜色 $0$ 没有进入阶段，只需倒序处理格子的首次改色。

做法

先扫描所有操作，为每个格子拆出若干三元组“颜色、开始时刻、结束时刻”。重复把同一格改为相同颜色不会产生新区间。

对每种非零颜色，将其区间按开始时刻递增排序。用并查集依次激活格子：新点使分量数增加一，与每个已经激活的同色邻格成功合并时再减一，把该增量记到开始时刻。

随后清空状态，把区间按结束时刻递减排序并再次加点。倒序加点的分量增量，正好是正序删除该点时分量数变化的相反数，因此把其相反数记到结束时刻。颜色 $0$ 只做这一步。

最后以初始全零矩阵的一个连通块为起点，对所有时刻增量求前缀和。

子任务 1 可在每次修改后直接 BFS 整张矩阵。子任务 2 只有零色和一种新颜色，可分别用一次正向与一次逆向并查集扫描。

复杂度

设有效颜色区间总数为 $K\le nm+q$。各颜色内排序的总复杂度为 $O(K\log K)$，并查集合并总复杂度为 $O(K\alpha(nm))$，空间复杂度为 $O(K+nm+q)$。

正确性证明

固定颜色 $c$。在正向进入阶段，并查集在每个开始时刻后恰好包含当时值为 $c$ 的全部格子，所以记录的是该颜色分量数的真实增加量。进入阶段结束后不再有新格子获得 $c$；把删除序列倒放就成为纯加点序列，因此倒序加点增量取反后，恰好是正序结束时刻的真实变化量。颜色 $0$ 同理，只是所有格子从时刻零开始存在。

不同颜色的格子永不属于同一连通块，所以各颜色分量数可以直接相加。汇总所有颜色在每个时刻的变化并求前缀和，得到每次操作后的全矩阵连通块数。