## Bulbel

设 $w=2^k$。我们可以一层一层进行这个分治过程：

- 第一步，将左下 $2^{k-1}\times 2^{k-1}$ 和右上 $2^{k-1}\times 2^{k-1}$ 子矩阵交换位置。

- 第二步，对于四个 $2^{k-1}\times 2^{k-1}$ 子矩阵，将其中左上 $2^{k-2}\times 2^{k-2}$ 和右下 $2^{k-2}\times 2^{k-2}$ 子矩阵交换位置。

- ......

- 最后一步，对于 $2^{2k-2}$ 个 $2\times 2$ 子矩阵，交换左下和右上元素。

可以发现，第 $i$ 步中，我们总是将第 $j$ 行和第 $j+2^{k-i}$ 行的某个相同的模式（但是进行了移位）进行交换（比如第一步模式是 $00001111/11110000$，第二步模式是 $00110011/11001100$）。我们只要预处理出这个模式，将它 $\operatorname{and}$ 到对应行上，然后交换过来即可。

操作次数为 $O(w\log w)$。