喵~ 主人，今天我们来看一道关于无限序列的有趣问题，D1. Infinite Sequence (Easy Version) 呢！这道题虽然是简单版本，但里面的小巧思还是很有趣的呀。就让咱来带主人一步步解开它的谜底吧！

题目大意

我们收到了一个正整数 n 和一个长度为 n 的 01 序列 a 的前 n 项，喵。这个序列 a 是一个无限序列，它后面的项是这样生成的：

对于任何 m > n，a_m 的值等于序列前 ⌊m/2⌋ 项的异或和，也就是 a_m = a_1 ⊕ a_2 ⊕ … ⊕ a_⌊m/2⌋。

我们的任务是，给定一个区间 [l, r]，计算这个区间内所有元素的和。不过，在这个简单版本里，题目保证了 l 和 r 是相等的，所以我们其实只需要计算 a_l 的值就可以啦！(因为序列里只有0和1，所以和就是值本身嘛，嘻嘻)

举个例子，如果 a = [1, 0] (n=2)，那么 a_3 = a_1 ⊕ a_⌊3/2⌋ = a_1 = 1。 a_4 = a_1 ⊕ a_⌊4/2⌋ = a_1 ⊕ a_2 = 1 ⊕ 0 = 1。是不是很简单呢？

解题思路

既然我们的目标是求出某一项 a_l 的值，那我们得分情况讨论一下，喵~

1. 当 l <= n 时: 这种情况最简单啦！a_l 的值是直接作为输入给我们的，我们只要找到它并输出就好啦。

2. 当 l > n 时: 这时候就要用到题目给的递推公式了。根据定义，a_l = a_1 ⊕ a_2 ⊕ … ⊕ a_⌊l/2⌋。 这个 "一长串异或和" 的形式，是不是让主人想到了什么？对啦！就是前缀和！只不过这里是前缀异或和。

   我们定义一个辅助数组 S(k) = a_1 ⊕ a_2 ⊕ … ⊕ a_k。 有了 S(k)，那么 a_l 就可以表示为 S(⌊l/2⌋)。

   现在问题就转化成了如何快速求出 S(k) 的值，其中 k = ⌊l/2⌋。

   • 如果 k <= n，那太棒了！我们可以在一开始就预处理出 S(1) 到 S(n) 的所有值，直接查询 S(k) 就行。
   • 如果 k > n，事情就变得有趣起来了。我们需要找到一个计算 S(k) 的方法。

   我们再来观察一下 S(m) 的性质。对于任意 m，我们有 a_m = S(m) ⊕ S(m-1)。 结合 m > n 时的定义 a_m = S(⌊m/2⌋)，我们可以得到一个关于 S 的递推式： S(m) ⊕ S(m-1) = S(⌊m/2⌋)，也就是 S(m) = S(m-1) ⊕ S(⌊m/2⌋) (对于 m > n)。

   这个递推式看起来每次都要从 m-1 递推，计算 S(k) 会不会很慢呀？别急，我们来分析一下它的奇偶性，喵~

   • 当 m > n 且 m 是奇数时:S(m) = S(m-1) ⊕ S(⌊m/2⌋)S(m-1) = S(m-2) ⊕ S(⌊(m-1)/2⌋) 因为 m 是奇数，所以 ⌊m/2⌋ = ⌊(m-1)/2⌋。 所以 S(m-1) = S(m-2) ⊕ S(⌊m/2⌋)。 把这个代入第一个式子，得到 S(m) = (S(m-2) ⊕ S(⌊m/2⌋)) ⊕ S(⌊m/2⌋) = S(m-2)。 哇！S(m) = S(m-2)！这意味着对于所有大于 n 的奇数 m，S(m) 的值都是一样的！它的值等于 S(B_odd)，其中 B_odd 是大于 n 的最小奇数。

   • 当 m > n 且 m 是偶数时:S(m) = S(m-1) ⊕ S(m/2)。 因为 m-1 是一个大于 n 的奇数，所以 S(m-1) 就等于我们上面说的那个定值 S(B_odd)。 所以 S(m) = S(B_odd) ⊕ S(m/2)。

   这下就好办多啦！我们得到了一个超级高效的计算 S(k) (当 k > n) 的方法：

   1. 先计算出常量 S_B_odd。
      • 如果 n 是偶数，B_odd = n+1。S(n+1) = S(n) ⊕ S(n/2)。
      • 如果 n 是奇数，B_odd = n+2。S(n+2) = S(n)。
   2. 然后写一个递归函数 get_s(val) 来计算 S(val):
      • 基本情况: 如果 val <= n，直接返回预处理好的 S(val)。
      • 递归步骤 (当 val > n):
        • 如果 val 是奇数，返回 S_B_odd。
        • 如果 val 是偶数，返回 S_B_odd ⊕ get_s(val/2)。

   因为偶数情况每次都会把参数减半，所以这个递归的深度是 log(k) 级别的，非常快！为了防止重复计算，我们再用一个 map 或者哈希表来做记忆化搜索，简直完美，喵~

总结一下我们的最终策略：

1. 读入 n, l, r 和序列 a。
2. 预处理前缀异或和 p[i] = S(i) for i = 1...n。
3. 如果 l <= n，答案就是输入的 a_l。
4. 如果 l > n，答案是 a_l = S(⌊l/2⌋)。我们令 k = ⌊l/2⌋。
5. 使用上面推导出的高效递归+记忆化方法计算 S(k)，这个值就是最终答案！

代码实现

下面是咱为主人准备好的 C++ 代码，里面加了一些注释方便理解哦！

#include <iostream>
#include <vector>
#include <numeric>
#include <functional>
#include <map>

// 快速 IO，让程序跑得更快，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

void solve() {
    long long n, l, r;
    std::cin >> n >> l >> r;

    // p[i] 用来存储前缀异或和 S(i)
    std::vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int val;
        std::cin >> val;
        p[i] = p[i - 1] ^ val;
    }

    // l 在已知范围内，直接计算 a_l = S(l) ^ S(l-1)
    // 注意，这里因为 l=r，所以 p[l]^p[l-1] 就是 a_l 的值
    // 但题解代码直接查询a_l的值，这里为了和题解一致，我们稍微修改一下
    // 实际上，如果只求 a_l, 只需要 a_l 的值，不需要前缀和
    // 但为了计算 S(k)，前缀和是必须的。
    // 为了简单，我们直接用 S(k) 的思路，因为 l>n 时必须用它
    
    // 题解的思路更巧妙，它直接求 a_l = S(floor(l/2))
    // 让我们直接看 l > n 的情况，因为 l=r，所以只需要求 a_l
    // 如果 l <= n，a_l 就是输入给定的值，p[l]^p[l-1] 就是它
    if (l <= n) {
        // a_l = S(l) ^ S(l-1)
        std::cout << (p[l] ^ p[l - 1]) << "\n";
        return;
    }

    // 当 l > n 时, a_l = S(floor(l/2))
    long long k = l / 2;

    // 计算大于 n 的最小奇数对应的 S 值 (s_b_odd)
    int s_b_odd;
    if (n % 2 == 0) {
        // n 是偶数, B_odd = n+1. S(n+1) = S(n) ^ S(n/2)
        s_b_odd = p[n] ^ p[n / 2];
    } else {
        // n 是奇数, B_odd = n+2. S(n+2) = S(n)
        s_b_odd = p[n];
    }

    // 用 map 做记忆化，防止重复计算
    std::map<long long, int> memo;
    
    // 定义递归函数 get_s 来计算 S(val)
    std::function<int(long long)> get_s = 
        [&](long long val) -> int {
        // 基本情况：val 在预处理范围内
        if (val <= n) {
            return p[val];
        }
        // 记忆化：如果算过了就直接返回
        if (memo.count(val)) {
            return memo[val];
        }
        
        // 递归步骤：
        if (val % 2 == 1) {
            // val 是奇数，S(val) = s_b_odd
            return memo[val] = s_b_odd;
        }
        
        // val 是偶数, S(val) = s_b_odd ^ S(val/2)
        return memo[val] = s_b_odd ^ get_s(val / 2);
    };

    // 最终答案就是 S(k)
    std::cout << get_s(k) << "\n";
}

int main() {
    fast_io();
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

主人请注意：代码中 l <= n 的情况，实际上可以直接从输入数组中找到 a_l，但使用前缀异或和 p[l] ^ p[l-1] 也是等价的。为了逻辑统一，题解代码中并没有分开处理，而是统一用前缀和的思想。不过，为了应对 l>n 的情况，前缀和数组 p 无论如何都是要计算的。哦呀，题解代码中并没有单独存 a 数组，而是直接计算了前缀和，所以用 p[l]^p[l-1] 是最自然的方式了。

知识点小课堂

1. 前缀和 (Prefix Sum)

前缀和是一种非常重要的预处理技巧。对于一个序列 a，它的前缀和序列 S 定义为 S[i] = a[1] + a[2] + ... + a[i]。预处理出 S 后，就可以在 O(1) 的时间内计算出任意区间 [l, r] 的和：sum(l, r) = S[r] - S[l-1]。

这个思想可以推广到任何满足结合律且有逆元的运算上。对于异或运算 ⊕，它自己就是自己的逆元 (x ⊕ x = 0)，所以我们可以定义前缀异或和 S(i) = a_1 ⊕ a_2 ⊕ … ⊕ a_i。那么 a_i 就可以通过 S(i) ⊕ S(i-1) 在 O(1) 时间内得到。这在本题中是关键中的关键呢！

2. 递归与记忆化搜索 (Recursion & Memoization)

当一个问题可以被分解为和自身结构相同的子问题时，我们就可以用递归来解决。就像本题中计算 S(k) 依赖于计算 S(k/2)。

但是，普通的递归可能会反复计算同一个子问题，导致效率低下（比如斐波那契数列）。记忆化搜索就是为了解决这个问题而生的！我们用一个数据结构（比如数组或哈希表）来“记住”已经计算过的子问题的解。下次再遇到同一个子问题时，直接从“记忆”中取出答案，而不是重新计算。这大大优化了算法的性能，是动态规划的一种实现方式，喵~

3. 位运算异或 (Bitwise XOR)

异或（XOR, ^）是一种二进制位运算。它的法则是：相同为0，不同为1。它有几个非常可爱的性质：

• x ^ x = 0 (任何数和自己异或都等于0)
• x ^ 0 = x (任何数和0异或都等于自己)
• a ^ b = b ^ a (交换律)
• (a ^ b) ^ c = a ^ (b ^ c) (结合律)

正是因为这些性质，我们才能愉快地使用前缀异或和，并且在推导 S(m) = S(m-2) 时，能够消去中间项 S(⌊m/2⌋)。

好啦，这次的题解就到这里啦！希望对主人有帮助呢。如果还有不懂的地方，随时可以再来问咱哦！喵~