T1
线段树，每个节点 \([l,r]\) 维护 \(c_l,c_r\) 和答案。
考虑如何上传。
如果 \(c_{mid} \ne c_{mid + 1}\)，答案 \(=\) 左儿子答案 \(+\) 右儿子答案。
否则，答案 \(=\) 左儿子答案 \(+\) 右儿子答案 \(- \ 1\)。因为两个连通块合并了。
T3
继续线段树，每个节点 \([l,r]\) 表示第 \(l\) 行到第 \(r\) 行，维护 \(l\) 行的字符，\(r\) 行的字符和答案。
首先我们忽略查询的列限制。
考虑上传。
我们继续沿用上面的做法，如果第 \(mid\) 行和第 \(mid + 1\) 行同一个位置的两个字符相同，而且他们还不在同一个连通块内，他们就所在的连通块会被合并成一个。
于是我们从左到右依次合并。过程中用并查集维护。
但是子矩阵修改，除了行限制还有列限制。如果节点继续维护 \([u,d]\) 列，时间爆炸。
我们考虑差分。对于节点 \([l,r]\) 它的每个前缀 \([1,i]\) 列，都维护出 \([l,r]\) 行 \([1,i]\) 列的连通块数量。上传和上面的做法没有差别。
我们已经得到了 \([l,r]\) 行 \([1,u]\) 列的连通块和 \([l,r]\) 行 \([1,d]\) 列的连通块数量，可以反推答案了。
注意到，我们在线段树上传子节点信息的时候，我们通过 \([l,mid]\) 行的答案和 \([mid + 1,r]\) 行的答案推出了 \([l,r]\) 行的答案。我们同样可以通过 \([l,r]\) 行的答案和 \([l,mid]\) 行的答案反推 \([mid + 1,r]\) 的答案。同时，这个做法对列也适用。
时间复杂度 \(O((n + q) n \log_2{n} \alpha(n))\)。
T2
数据范围变大了，但是有特殊性质，不再需要并查集维护连通块了。具体见代码。
时间复杂度 \(O((n + q) n \log_2 n)\)。
结语
感谢 wzy，让我重新找到了快乐。