#P11696. [JRKSJ ExR] 七影蝶

[JRKSJ ExR] 七影蝶

题目背景

题目描述

久岛鸥给了你一个长度为 nn 的非负整数序列 a1na_{1\sim n}

接下来有 qq 次询问,每次询问给出非负整数 L,RL,R,求

$$\max_{x=L}^R\left(\sum_{i=1}^n\mathrm{popcount}(a_i+x)\right) $$

其中 popcount(x)\mathrm{popcount}(x) 表示 xx 在二进制形式下数位 11 的出现次数。

输入格式

第一行,两个整数 n,qn,q
第二行给出 nn 个整数代表序列 a1na_{1\sim n}
随后 qq 行,每行两个整数 L,RL,R,代表一次询问。

输出格式

输出 qq 行,第 ii 行一个整数代表第 ii 次询问的答案。

6 6
1 1 4 5 1 4
1 10
1 5
3 6
4 7
3 9
2 5
19
13
16
16
16
13
10 10
765 523 255 781 647 98 451 636 109 771
394 405
128 161
332 565
996 1003
3 116
403 486
255 582
744 861
399 408
528 996
58
59
69
68
66
62
69
75
58
75

提示

样例解释

对于样例 11,第一组询问取 x=10x=10 时达到最大值,即 $\mathrm{popcount}(11)\times 3+\mathrm{popcount}(14)\times 2+\mathrm{popcount}(15)=3\times 3+2\times 3+4=19$。

容易验证 xx 取范围内其他值都不能使答案更大。

数据范围

本题开启捆绑测试。

VV 为数组中元素与询问区间端点的最大值。

Subtask\text{Subtask} nn\le qq\le VV\le Score\text{Score}
11 1010 55
22 10510^5 5×1055\times 10^5 10310^3
33 10510^5 1515
44 10410^4 10910^9 1010
55 10510^5 11 1515
66 5×1055\times 10^5 2020
77 5×1055\times 10^5 10510^5
88 5×1055\times 10^5 1010
99 101110^{11} 00

对于所有数据,保证 1n,q5×1051\le n,q\le 5\times 10^50LR10110\le L\le R\le 10^{11}0ai10110\le a_i\le 10^{11}

子任务 6,7,96,7,9 的时间限制为 55 秒,其余子任务均为 33 秒。