一、思路

首先对于公式我们可以注意到：

$t=(s_l \space \text{and}\space s_{l+1} \space \text{and } \cdots \text{ and } s_r) \text{ xor } (\text{not }(s_l \text{ or } s_{l+1} \text{ or } \cdots \text{ or } s_r))$

$\forall k \space (1 \leq k \leq m)$ 如果要对答案有贡献就要使 $s$ 的第 $k$ 列的第 $l$ 行到第 $r$ 行都是相同的数

 为什么呢

 如果当前第 $k$ 列对答案的贡献为 $0$

那么显而易见 $xor$ 前后两个式子都必须全为 $1$ 或全是 $0$，考虑全为 $0$ 的情况，对于前一个式子可能 $l \sim r$ 行全是 $0$ 或两种数都有，思考一下就能发现只有当两种数都有的时候才会使答案的贡献为 $0$。

再考虑一下如果前后两个式子全为 $1$，那么对于前一个式子就必须使 $l \sim r$ 行都为 $1$，但显然不可以的，所以就不再考虑。

综上所述如果想让当前第 $k$ 列对答案的贡献为 $1$ 那么 $l \sim r$ 每一个数都为同一种（$0$ 或 $1$）

二、实现

第一关

想必如果理解了以上思路，就很容易想到前缀和（似乎可以用树状数组（doge）），具体怎么实现也很简单根据题目数据会发现一个很奇妙的东西 $nm \leq 1e7$ 这意味着如果我们在主函数中直接定义并初始化时间复杂度是 $O(nm)$ 的！这样便可以建立数组而不超时了。

接下来定义数组 $sum_i,_j$ 表示第 $j$ 列，$1 \sim i$ 的行的前缀和，那么查询时只需要判断 $sum_{l -1},_j \space - \space sum_r,_j$ 是否全为 $0$ 或全为 $1$ 就行了

第二关

还有第二关，发现 $k$ 最大为 $2 * 10^6$ 这是很大的，意味着我们的查询 $l,r$ 完全有可能重复！所以我们可以用 hash 来优化一下（当然一些别的优化，例如：循环节优化 也可以），将每一个 $l,r$ 都变为 $1$ 个 $n$ 进制数，具体为 $l * n + r$，将转化后的数扔进 $map$（当然要用 $unordered \space map$ 优化），每次看 $l,r$ 是否重复即可

第二种实现

即二分做法，我会用另外一篇题解讲述。

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

orz

OTZ