P15276 [MCO 2025] Long Binary String

A long binary string is formed via the following process: 1. Start with the string $\tt{1}$. 2. Every second, we replace each $\tt{1}$ of the current string with $\tt{10}$ and each $\tt{0}$ of the current string with $\tt{1}$. The state of the string in the first few seconds is as follows: $1, 10, 101, 10110, 10110101$. Let $s$ be the string obtained at the end of the process after running it for $10^{100}$ seconds. You want to answer $Q$ queries of the following type: how many ones are there between the $l$-th character and $r$-th character (inclusive) of $s$?

The first line contains a single integer $Q$ ($1 \le Q \le 300\,000$), denoting the number of queries. The next $Q$ lines each contain two space-separated integers $l,r$ ($1 \le l \le r \le 10^{18}$), representing the queries.

For each query, output the number of ones between the $l$-th character and $r$-th character (inclusive) of $s$.

### Note One can show that the first $12$ characters of the string are $101101011011$. For the first query, there are $5$ ones between the 3rd character and 9th character. The relevant substring is $1101011$. For the second query, there is $1$ one between the 6th character and 6th character. The relevant substring is $1$. For the third query, there are $8$ ones between the 1st character and 12th character. The relevant substring is $101101011011$. ### Scoring Subtask $1$ ($7$ points): $Q = 1$, $r \le 300\,000$ Subtask $2$ ($10$ points): $l = 1$, $r \le 300\,000$ Subtask $3$ ($13$ points): $r \le 300\,000$ Subtask $4$ ($20$ points): $l=1$, $r$ is equal to the length of the string after some integer number of seconds. Subtask $5$ ($15$ points): $l=r$ Subtask $6$ ($15$ points): $Q = 1$ Subtask $7$ ($10$ points): $r \le 10^9$ Subtask $8$ ($10$ points): No additional constraints