首先可以将题面转化为查询 l∼r 中,有几位上只出现 0 或只出现 1。
我们考虑一个朴素的做法,当 m 足够小时,我们 O(nm) 预处理变更位置的前缀和,然后每次遍历 m 位,O(1) 查看是否有变更位置即是否有贡献,这个做法的复杂度为 O(m(n+k)),能通过 m≤100 的测试点。
从另一方面,n 小时,我们希望可以处理出所有答案。我们研究每一位会给哪些区间做贡献,将其放到数组上,做二维前缀和,这个做法的复杂度为 O(n2+nm+k),能通过 n≤104 的测试点。
由于 nm≤106,故有 m≤100 或 n≤104 成立,我们做测试点分治即可通过本题。
感觉这个做法挺胡扯的,不过能过...
代码见本人 提交记录