CF2071D2.Infinite Sequence (Hard Version)

这是该问题的困难版本。不同版本的区别在于此版本中 $l \leq r$。仅当您解决了该问题的所有版本时才能进行 hack。

给定一个正整数 $n$ 和一个无限二进制序列 $a$ 的前 $n$ 项，该序列定义如下：

• 对于 $m > n$，$a_m = a_1 \oplus a_2 \oplus \ldots \oplus a_{\lfloor \frac{m}{2} \rfloor}$ $^{\text{∗}}$。

你的任务是计算给定区间 $[l, r]$ 内元素的和：$a_l + a_{l + 1} + \ldots + a_r$。

$^{\text{∗}}$ $\oplus$ 表示按位异或操作。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$l$ 和 $r$（$1 \le n \le 2 \cdot 10^5$，$1 \le l \leq r \le 10^{18}$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$\color{red}{a_i \in \{0, 1\}}$）——序列 $a$ 的前 $n$ 项。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数——给定区间内元素的和。

在第一个测试用例中，序列 $a$ 为：

$$[\underline{\color{red}{1}}, 1, 1, 0, 0, 1, 1, 1, 1, 1, \ldots]$$

其中 $l = 1$，$r = 1$。区间 $[1, 1]$ 的元素和为 $a_1 = 1$。

在第二个测试用例中，序列 $a$ 为：

$$[\text{\color{red}{1}}, \text{\color{red}{0}}, \underline{1}, 1, 1, 0, 0, 1, 1, 0, \ldots]$$

其中 $l = 3$，$r = 10$。区间 $[3, 10]$ 的元素和为

$$a_3 + a_4 + \ldots + a_{10} = 1 + 1 + 1 + 0 + 0 + 1 + 1 + 0 = 5.$$

翻译由 DeepSeek R1 完成