P11696 [JRKSJ ExR] 七影蝶


久岛鸥给了你一个长度为 $n$ 的非负整数序列 $a_{1\sim n}$。 接下来有 $q$ 次询问，每次询问给出非负整数 $L,R$，求 $$\max_{x=L}^R\left(\sum_{i=1}^n\mathrm{popcount}(a_i+x)\right)$$ 其中 $\mathrm{popcount}(x)$ 表示 $x$ 在二进制形式下数位 $1$ 的出现次数。

第一行，两个整数 $n,q$。 第二行给出 $n$ 个整数代表序列 $a_{1\sim n}$。 随后 $q$ 行，每行两个整数 $L,R$，代表一次询问。

输出 $q$ 行，第 $i$ 行一个整数代表第 $i$ 次询问的答案。

### 样例解释 对于样例 $1$，第一组询问取 $x=10$ 时达到最大值，即 $\mathrm{popcount}(11)\times 3+\mathrm{popcount}(14)\times 2+\mathrm{popcount}(15)=3\times 3+2\times 3+4=19$。 容易验证 $x$ 取范围内其他值都不能使答案更大。 ### 数据范围 **本题开启捆绑测试。** 令 $V$ 为数组中元素与询问区间端点的最大值。 ::cute-table | $\text{Subtask}$ | $n\le$ | $q\le$ | $V\le$ |$\text{Score}$ | | :-----------: | :-----------: | :-----------: | :---------: | :----------: | |$1$ | $10$| $10$ | $10$ | $5$ | $2$ |$2$ | $10^5$| $5\times 10^5$ | $10^3$ | $5$ | $2$ |$3$ | ^| $10^5$ | $10^5$ | $15$ | $2$ |$4$ | $10^4$| $10^4$ | $10^9$ | $10$ | $2$ |$5$ | $10^5$| $1$ | ^ | $15$ | $2$ |$6$ | ^| $5\times 10^5$ | ^ | $20$ | $5$ | $7$ | $5\times 10^5$ | $10^5$ | ^ | $20$ | $5$ | $8$ | ^ | $5\times 10^5$ | ^ | $10$ | $2$ | | $9$ | ^ | ^ | $10^{11}$ | $0$ | 对于所有数据，保证 $1\le n,q\le 5\times 10^5$，$0\le L\le R\le 10^{11}$，$0\le a_i\le 10^{11}$。 子任务 $6,7,9$ 的时间限制为 $5$ 秒，其余子任务均为 $3$ 秒。