P15276 [MCO 2025] Long Binary String

一个很长的二进制字符串通过以下过程生成： 1. 从字符串 $\tt{1}$ 开始。 2. 每一秒，我们将当前字符串中的每个 $\tt{1}$ 替换为 $\tt{10}$，并将每个 $\tt{0}$ 替换为 $\tt{1}$。 前几秒字符串的状态如下： $1, 10, 101, 10110, 10110101$。 令 $s$ 为这个过程执行了 $10^{100}$ 秒后得到的字符串。你需要回答 $Q$ 个如下形式的查询： $s$ 中从第 $l$ 个字符到第 $r$ 个字符（包含两端）之间有多少个 $1$？

第一行包含一个整数 $Q$ （$1 \le Q \le 300\,000$），表示查询的数量。 接下来的 $Q$ 行，每行包含两个以空格分隔的整数 $l, r$ （$1 \le l \le r \le 10^{18}$），代表查询。

对于每个查询，输出 $s$ 中从第 $l$ 个字符到第 $r$ 个字符（包含两端）之间 $1$ 的个数。

#### 注释 可以证明，该字符串的前 $12$ 个字符是 $101101011011$。 对于第一个查询，第 $3$ 个字符到第 $9$ 个字符之间有 $5$ 个 **1**，相关的子串是 $1101011$。 对于第二个查询，第 $6$ 个字符到第 $6$ 个字符之间有 $1$ 个 **1**，相关的子串是 $1$。 对于第三个查询，第 $1$ 个字符到第 $12$ 个字符之间有 $8$ 个 **1**，相关的子串是 $101101011011$。 #### 计分 **子任务 $1$** （$7$ 分）： $Q = 1$， $r \le 300\,000$ **子任务 $2$** （$10$ 分）： $l = 1$， $r \le 300\,000$ **子任务 $3$** （$13$ 分）： $r \le 300\,000$ **子任务 $4$** （$20$ 分）： $l=1$， $r$ 等于某个整数秒后字符串的长度 **子任务 $5$** （$15$ 分）： $l=r$ **子任务 $6$** （$15$ 分）： $Q = 1$ **子任务 $7$** （$10$ 分）： $r \le 10^9$ **子任务 $8$** （$10$ 分）： 无额外限制 翻译由 DeepSeek 完成