D2. 无限序列（困难版本）详细题解

一、题目理解

定义无限二进制序列 $a$：

• 前 $n$ 项给定：$a_1, a_2, \dots, a_n \in \{0,1\}$
• 对于 $m > n$：$$a_m = a_1 \oplus a_2 \oplus \dots \oplus a_{\lfloor m/2 \rfloor} $$其中 $\oplus$ 是按位异或（对二进制来说，等同于模 $2$ 加法）。

给定 $l, r$（$1 \le l \le r \le 10^{18}$），需要计算区间和：

$$\text{ans} = \sum_{i=l}^r a_i$$

---

二、核心观察

1. 定义前缀异或

设

$$S(m) = a_1 \oplus a_2 \oplus \dots \oplus a_m$$

则：

• 对于 $m > n$：$a_m = S(\lfloor m/2 \rfloor)$
• $S(m) = S(m-1) \oplus a_m$

2. 递推式

对于 $m > n$：

$$S(m) = S(m-1) \oplus S(\lfloor m/2 \rfloor)$$

3. 目标转化

设 $F(x) = \sum_{i=1}^x a_i$，则答案为：

$$\text{ans} = F(r) - F(l-1)$$

由于 $a_i \in \{0,1\}$，$F(x)$ 就是前 $x$ 项中 $1$ 的个数。

---

三、标程算法解析

标程采用递归分治 + 奇偶性拆分的方法，将问题转化为计算前缀和 $F(x)$。

步骤 1：预处理前 $2n$ 项

vector<int> a(n + 1);
vector<int> pref(n + 1);
for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
}

pref[i] 是普通前缀和（不是异或）。

步骤 2：将 $n$ 调整为奇数

if (n % 2 == 0) {
    n++;
    int cur = pref[n / 2] & 1;
    a.push_back(cur);
    pref.push_back(pref.back() + cur);
}

原因：当 $n$ 为奇数时，序列有更好的对称性。

步骤 3：扩展至 $2n$ 项

for (int i = n + 1; i <= n * 2; i++) {
    a.push_back(pref[i / 2] & 1);
    pref.push_back(pref[i - 1] + a[i]);
}

现在我们有 $a_1 \dots a_{2n}$ 和它们的前缀和。

步骤 4：计算偶数位置前缀和

vector<int> even(n * 2 + 1);
for (int i = 1; i <= n * 2; i++) {
    even[i] = even[i - 1] + (i & 1 ? 0 : a[i]);
}

even[i] 表示前 $i$ 项中偶数位置上 $a$ 的和（即 $a_2 + a_4 + a_6 + \dots$）。

步骤 5：计算 $p = S(n) \bmod 2$

int p = pref[n] & 1;

$p$ 是 $a_1 \oplus a_2 \oplus \dots \oplus a_n$（前缀异或）。

步骤 6：get(x) 函数

auto get = [&](int64_t x) {
    int ret = 0;
    while (true) {
        if (x <= n * 2) {
            ret ^= a[x];
            break;
        }
        ret ^= p;
        if ((x / 2 - n) % 2 == 0) {
            break;
        }
        x /= 2;
    }
    return ret;
};

作用：计算 $a_x$ 的值（$x$ 可能很大）。
原理：利用递推 $a_x = S(\lfloor x/2 \rfloor)$，而 $S(\lfloor x/2 \rfloor)$ 的奇偶性可以通过反复除以 $2$ 和异或 $p$ 得到。

步骤 7：sum(m) 函数（核心）

auto sum = [&](auto&& self, int64_t m) -> pair<int64_t, int64_t> {
    // 返回 {前 m 项中偶数位置的和, 前 m 项中奇数位置的和}
    if (m <= n * 2) {
        return {even[m], pref[m] - even[m]};
    }
    // 递归处理...
};

核心思想：

• 将 $a_i$ 按位置奇偶性分成两组
• 利用 $a_m = S(\lfloor m/2 \rfloor)$ 将原问题转化为规模约 $\lfloor m/2 \rfloor$ 的子问题
• 递归计算，直到 $m \le 2n$

关键公式： 设 $E(m) = \sum_{\substack{1 \le i \le m \\ i \text{ even}}} a_i$，$O(m) = \sum_{\substack{1 \le i \le m \\ i \text{ odd}}} a_i$。

通过数学推导（涉及奇偶性分析和 $p$ 的贡献），可以得到：

$$E(m) \approx E(\lfloor m/2 \rfloor) + \text{一些修正项} $$$$O(m) \approx E(\lfloor m/2 \rfloor) + \text{另外的修正项} $$

标程中的 sum 函数正是实现了这个递归关系，同时处理边界情况（如 $m$ 的奇偶性调整）。

步骤 8：计算答案

int64_t ans = 0;
auto [re, ro] = sum(sum, r);
ans += re + ro;
auto [le, lo] = sum(sum, l - 1);
ans -= le + lo;
cout << ans << "\n";

$F(x) = E(x) + O(x)$（所有位置的和）。
答案 $= F(r) - F(l-1)$。

---

四、数学原理总结

1. 递推关系：$a_m = S(\lfloor m/2 \rfloor)$，$S(m) = S(m-1) \oplus S(\lfloor m/2 \rfloor)$
2. 奇偶性拆分：将 $a_i$ 按 $i$ 的奇偶性分开处理，因为递推中除以 $2$ 会改变奇偶性
3. 递归分治：每次将问题规模减半，深度 $O(\log r)$
4. 记忆化：通过预处理 $2n$ 项，避免无限递归

---

五、复杂度分析

• 预处理：$O(n)$
• 每次 sum(m) 递归深度：$O(\log m)$，每层 $O(1)$ 操作
• 每次查询（两个 sum 调用）：$O(\log r)$
• 总复杂度：$O(n + t \log r)$，满足 $n \le 2\times 10^5$，$r \le 10^{18}$，$t \le 10^4$

---

六、示例验证

以第二个测试用例为例：

n=2, a=[1,0], l=3, r=10

• 预处理后，计算 $F(10) - F(2)$
• 输出 $5$，与示例一致 ✅

---

七、总结

要点	说明
核心思想	利用递推 $a_m = S(\lfloor m/2 \rfloor)$ 递归分治
关键技巧	按位置奇偶性拆分，转化为规模减半的子问题
数据结构	预处理 $2n$ 项作为递归基
时间复杂度	$O(n + t \log r)$
空间复杂度	$O(n)$