我并没有看出来“最后 bitset 中为 $1$ 的点 $j$ 是在 $i \in [l, r]$ 中 $s_{i, j}$ 全为 $0$ / 全为 $1$ 的。”这个关键结论（不会只有我一个人觉得这并不显然吧），但我们仍有一些比较直接的做法解决本题。

当 $n$ 较小时，暴力预处理出所有 $n^2$ 个数对的答案，时间复杂度 $O(n^2m) \sim O(1)$。

当 $m$ 较小时，考虑用数据结构来维护。能用的数据结构很多，从时间复杂度上考量可以用 ST 表（注意 $\operatorname{and}$ 和 $\operatorname{or}$ 都满足可重复贡献），时间复杂度 $O(mn \log n) \sim O(m)$。

直接这样写仍然无法通过本题，但加上手写 bitset 的优化就够了：方法 1 的时间复杂度降为 $O(\dfrac{n^2m}{w}) \sim O(1)$，方法 2 的时间复杂度降为 $O(\dfrac{mn \log n}{w}) \sim O(\dfrac{m}{w})$，其中 $w = 64$（如果用 unsingned long long 压位的话。）考虑到 $\min(n, m) \le 10^3$，可以通过。

这种做法的时间复杂度和代码实现难度都劣于正解，但无需发现正解所需的结论，仅供参考。

不用手写 bitset 的提交记录：link

手写 bitset 的提交记录：link