9410

P9410 待补：根号分治做法 发现要支持区间加和连通块求和、合并，容易想到分块（虽然我一开始看错题了）。 完全不需要根号分治，直接分块即可。 考虑稍微暴力的分块。区间加的话，散块部分可以直接加到全局的 \(sum\) 数组中，毕竟不是区间求和，然后整块部分直接打标记，记录块内每个连通块的大小即可。 ......

和 @ez_lcw 胡出来的做法，不需要什么高级科技。 先假设没有 $1$ 操作，变成初始给定若干连通块。该问题容易归约为矩阵乘法，$A$ 矩阵每行是一种颜色，$B$ 矩阵每列是一个操作。所以可以直接思考 $O(n\sqrt n)$ 的做法。 通过枚举做法，发现可以序列分块。对于每个块，维护散块加的 ......