首先可以将题面转化为查询 $l\sim r$ 中，有几位上只出现 $0$ 或只出现 $1$。

我们考虑一个朴素的做法，当 $m$ 足够小时，我们 $O(nm)$ 预处理变更位置的前缀和，然后每次遍历 $m$ 位，$O(1)$ 查看是否有变更位置即是否有贡献，这个做法的复杂度为 $O(m(n+k))$，能通过 $m\le 100$ 的测试点。

从另一方面，$n$ 小时，我们希望可以处理出所有答案。我们研究每一位会给哪些区间做贡献，将其放到数组上，做二维前缀和，这个做法的复杂度为 $O(n^2+nm+k)$，能通过 $n\le 10^4$ 的测试点。

由于 $nm\le 10^6$，故有 $m\le 100$ 或 $n\le 10^4$ 成立，我们做测试点分治即可通过本题。

感觉这个做法挺胡扯的，不过能过...

代码见本人 提交记录