题解满了，不是这个做法。

首先一个很基础的想法是对于每一行建一棵线段树，那么操作 $0$ 的时间复杂度为 $\mathcal O(1)$（因为是在线段树上直接对根节点打标记），操作 $1$ 的时间复杂度为 $\mathcal O(n\log m)$。太不平衡了。

容易想到的是，当 $n<m$ 时，对于每一行建一棵线段树；否则对于每一列建一棵线段树。这样，操作 $0$ 的时间复杂度为 $\mathcal O(1)$，操作 $1$ 的时间复杂度为 $\mathcal O(\min(n, m)\log \max(n, m))$。最坏情况下为 $\mathcal O(\sqrt{nm}\log \max (n, m))$。还是有点慢，当时民间 $80$ 分，官方 $90$。

刚才我脑子一闪，发现我是个智障。

当 $n<\sqrt[3]{nm}$ 时，对于每一行建一棵线段树；当 $m<\sqrt[3]{nm}$ 时，对于每一列建一棵线段树；否则，朴素暴力。虽然这东西还是能卡得挺慢，不过现在这个分类讨论还有点粗糙，可能还能优化？

官方数据过了。实测把临界值改成 $(nm)^{\frac{2}{5}}$ 会更快一点。

record