#P11696. [JRKSJ ExR] 七影蝶
[JRKSJ ExR] 七影蝶
题目背景
题目描述
久岛鸥给了你一个长度为 的非负整数序列 。
接下来有 次询问,每次询问给出非负整数 ,求
$$\max_{x=L}^R\left(\sum_{i=1}^n\mathrm{popcount}(a_i+x)\right) $$其中 表示 在二进制形式下数位 的出现次数。
输入格式
第一行,两个整数 。
第二行给出 个整数代表序列 。
随后 行,每行两个整数 ,代表一次询问。
输出格式
输出 行,第 行一个整数代表第 次询问的答案。
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
提示
样例解释
对于样例 ,第一组询问取 时达到最大值,即 $\mathrm{popcount}(11)\times 3+\mathrm{popcount}(14)\times 2+\mathrm{popcount}(15)=3\times 3+2\times 3+4=19$。
容易验证 取范围内其他值都不能使答案更大。
数据范围
本题开启捆绑测试。
令 为数组中元素与询问区间端点的最大值。
对于所有数据,保证 ,,。
子任务 的时间限制为 秒,其余子任务均为 秒。