P9986 [Ynoi2079] r2pspc

Given a sequence $a_1,\dots,a_n$ and $m$ queries, each query asks for the number of $1$ bits in the binary representation of $\sum\limits_{i=l}^r 2^{a_i}$.

The first line contains two integers $n, m$. The second line contains $n$ integers $a_1,\dots,a_n$. The next $m$ lines each contain $l, r$, representing one query.

Output $m$ lines. Each line is the answer to the corresponding query.

Idea: rushcheyo, Solution: djq_cpp&ccz181078, Code: ccz181078, Data: ccz181078. Constraints: For $100\%$ of the testdata, $1\le n\le {10}^5$, $1\le m\le {10}^6$, $1\le a_i\le 10^9$, $1\le l\le r\le n$. For $25\%$ of the testdata, $n, m\le 1000$. For another $25\%$ of the testdata, $a_i\le 100$. For another $25\%$ of the testdata, $m\le 10^5$. For the remaining $25\%$ of the testdata, there are no special constraints. Translated by ChatGPT 5