P11696 [JRKSJ ExR] Seven-Shadow Butterfly.


Kyujima Kamome gives you a non-negative integer sequence $a_{1\sim n}$ of length $n$. Then there are $q$ queries. Each query gives non-negative integers $L, R$. You need to compute $$\max_{x=L}^R\left(\sum_{i=1}^n\mathrm{popcount}(a_i+x)\right)$$ where $\mathrm{popcount}(x)$ denotes the number of $1$ bits in the binary representation of $x$.

The first line contains two integers $n, q$. The second line contains $n$ integers representing the sequence $a_{1\sim n}$. The following $q$ lines each contain two integers $L, R$, representing one query.

Output $q$ lines. The $i$-th line contains one integer representing the answer to the $i$-th query.

### Sample Explanation For sample $1$, the maximum is achieved when $x = 10$ in the first query, that is, $\mathrm{popcount}(11)\times 3+\mathrm{popcount}(14)\times 2+\mathrm{popcount}(15)=3\times 3+2\times 3+4=19$. It is easy to verify that choosing other values of $x$ within the range cannot make the answer larger. ### Constraints **This problem uses bundled subtasks.** Let $V$ be the maximum value among the array elements and the query endpoints. ::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$ | For all testdata, it is guaranteed that $1\le n, q\le 5\times 10^5$, $0\le L\le R\le 10^{11}$, and $0\le a_i\le 10^{11}$. The time limit for subtasks $6, 7, 9$ is $5$ seconds, and for the other subtasks it is $3$ seconds. Translated by ChatGPT 5