#P17425. 七影蝶
七影蝶
题目描述
久岛鸥给了你一个长度为 的非负整数序列 。
接下来有 次询问,每次询问给出非负整数 ,求
$$\max_{x=L}^R\left(\sum_{i=1}^n\mathrm{popcount}(a_i+x)\right)$$其中 表示 在二进制形式下数位 的出现次数。
输入格式
第一行,两个整数 。
第二行给出 个整数代表序列 。
随后 行,每行两个整数 ,代表一次询问。
输出格式
输出 行,第 行一个整数代表第 次询问的答案。
输入输出样例 #1
输入 #1
6 6
1 1 4 5 1 4
1 10
1 5
3 6
4 7
3 9
2 5
输出 #1
19
13
16
16
16
13
输入输出样例 #2
输入 #2
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
输出 #2
58
59
69
68
66
62
69
75
58
75
说明/提示
样例解释
对于样例 ,第一组询问取 时达到最大值,即 $\mathrm{popcount}(11)\times 3+\mathrm{popcount}(14)\times 2+\mathrm{popcount}(15)=3\times 3+2\times 3+4=19$。
容易验证 取范围内其他值都不能使答案更大。
数据范围
本 Hydro 版本所有测试点统一采用 5 秒时限、1920 MiB 内存限制;按测试点等分,共 100 分。
下表保留原题的数据分档和历史分值,作为范围说明。原资料对普通子任务的时间存在表格 2 秒、末文 3 秒的两种记录;本版本沿用现行 Hydro 配置的统一 5 秒限制。
令 为数组中元素与询问区间端点的最大值。
| 原分值 | 原表记录的时限(秒) | ||||
|---|---|---|---|---|---|
对于所有数据,保证 ,,。
本版本执行上述统一时限与计分方式。