U150104 不考位运算 2

RT，不考位运算的第 2 道，是 [U150094 不考位运算 ](https://www.luogu.com.cn/problem/U150094) 的简单加强版。

给定一长度为 $n$ 的数列 $a$，有 $m$ 次查询操作。每次查询给定四个正整数 $l_1,r_1,l_2,r_2$，求： $$\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}(a_i\oplus a_j) \pmod{10^9 + 7}$$ 其中 $\oplus$ 代表按位异或运算。

第 $1$ 行有两个整数 $n,m$，分别代表数列长度、询问次数。 第 $2$ 行有 $n$ 个整数，描述了给定的数列 $a$。 第 $3\sim m + 2$ 行每行有四个整数 $l_1,r_1,l_2,r_2$，描述了一次查询操作。

输出共 $m$ 行，第 $i$ 行代表第 $i$ 次查询的结果。

|测试点编号|$n,m\le$|特殊性质| |-|-|-| |$1\sim 6$|$100$|无| |$7\sim 8$|$10^3$|保证每次询问的 $l_1 = 1, r_1 = n$| |$9\sim 12$|$5\times 10^5$|$a_i\le 8$| |$11\sim 20$|$5\times 10^5$|无| 对于所有测试点，$1\le n,m\le 5\times 10^5$，$0\le a_i\le 10^9$。 测试点 $9\sim 20$ 输入量约 20MB，请使用较快的读入方式。 ## Sol 异或运算仅关注两数每一位是否相同，考虑拆位，对每个数进行二进制分解，用前缀和分别维护每一位上 0/1 的个数。查询时取出两区间中各位 0/1 的个数，考察与每位不同的数的对数，统计贡献即可。 总复杂度 $O((n+m)\log w)$ 级别，其中 $w\approx 30$，为二进制位数。