题目描述

我们有一排 $n$ 个史莱姆，第 $i$ 个的体重为 $w_i$。
史莱姆的吃法规则是：如果史莱姆 $i$ 的体重 $w_i$ 大于或等于其相邻的史莱姆 $j$ 的体重 $w_j$ ($w_i \ge w_j$)，那么 $i$ 可以吃掉 $j$。吃掉后，$j$ 消失，$i$ 的体重更新为 $w_i \oplus w_j$（$\oplus$ 是按位异或）。

现在要进行一个实验：
1. 在 $n$ 个史莱姆的最右边（索引 $n$ 的位置）添加一个新的史莱姆，其体重为给定的参数 $x$。
2. 这个新添加的史莱姆（我们称之为“玩家史莱姆”）开始尝试吃掉它左边的邻居。
3. 如果玩家史莱姆能吃掉左边的邻居（设邻居索引为 $j$，玩家史莱姆体重为 $w_{player}$，邻居体重为 $w_j$，条件是 $w_{player} \ge w_j$），则：
* 邻居 $j$ 消失。
* 玩家史莱姆的体重更新为 $w_{player} \leftarrow w_{player} \oplus w_j$。
* 玩家史莱姆移动到原来邻居 $j$ 的位置。
4. 玩家史莱姆重复步骤 3，不断尝试吃左边的邻居，直到它左边没有史莱姆了，或者它无法吃掉左边的邻居（因为体重不够大）。
5. 注意：在这个过程中，只有玩家史莱姆会吃，其他史莱姆之间不发生互相吃的情况。
6. 实验的 得分 定义为玩家史莱姆总共吃掉的史莱姆数量。

你需要回答 $q$ 次独立的询问。每次询问给定一个参数 $x$，计算对应的实验得分。每次询问都是独立的，不影响原始的 $n$ 个史莱姆的状态。

样例

输入:
3
1 1
5
6
4 4
1 5 4 11
8
13
16
15
10 9
10 4 3 9 7 4 6 1 9 4
2
6
5
6
9
8
6
2
7

输出:
1
0 2 4 2
0 1 1 1 3 3 1 0 1

样例 2 解释

• 初始 $w = [1, 5, 4, 11]$。
• 询问 $x=8$:
  • 状态变为 $[1, 5, 4, 11, \underline{8}]$。
  • 玩家史莱姆 (8) 尝试吃左边的 11。 $8 < 11$，不能吃。
  • 过程停止。吃掉 0 个史莱姆，得分 0。
• 询问 $x=13$:
  • 状态变为 $[1, 5, 4, 11, \underline{13}]$。
  • 玩家 (13) 尝试吃 11。 $13 \ge 11$。吃掉。
  • 玩家体重变为 $13 \oplus 11 = 6$。
  • 状态变为 $[1, 5, 4, \underline{6}]$。
  • 玩家 (6) 尝试吃 4。 $6 \ge 4$。吃掉。
  • 玩家体重变为 $6 \oplus 4 = 2$。
  • 状态变为 $[1, 5, \underline{2}]$。
  • 玩家 (2) 尝试吃 5。 $2 < 5$。不能吃。
  • 过程停止。吃掉了 11 和 4，共 2 个史莱姆，得分 2。

算法 (预计算 + 倍增/二进制分组思想)

$O((N+Q)\log W)$ 其中 W 是最大体重

思路分析

1. 模拟与瓶颈:
   直接模拟每次询问的过程。玩家史莱姆从右到左，逐个检查是否能吃掉左边的史莱姆。如果能吃，更新体重，继续向左。这个过程最坏情况下需要 $O(N)$ 步（吃掉所有 $N$ 个史莱姆）。对于 $Q$ 次询问，总复杂度为 $O(N \cdot Q)$，这对于 $N, Q \le 2 \cdot 10^5$ 太慢了。我们需要优化。

2. 优化方向:
   模拟过程中的瓶颈在于逐个检查史莱姆。我们希望能够一次性“跳过”或处理掉一批史莱姆。
   观察玩家史莱姆 $P$ 和其左邻居 $L$ 的交互：

   • 如果 $w_P \ge w_L$，则 $P$ 吃掉 $L$， $w_P \leftarrow w_P \oplus w_L$。
   • 如果 $w_P < w_L$，则 $P$ 停止。
     比较大小主要看最高有效位 (Most Significant Bit, MSB)。设 $d_P = \lfloor \log_2 w_P \rfloor$ 和 $d_L = \lfloor \log_2 w_L \rfloor$。
   • 如果 $d_P > d_L$，则 $w_P > w_L$，一定能吃。
   • 如果 $d_P < d_L$，则 $w_P < w_L$，一定不能吃，停止。
   • 如果 $d_P = d_L$，需要比较具体的数值。

3. 利用位运算性质:
   XOR 操作可能会改变 MSB。但是，如果 $d_P > d_L$，那么 $w_P \oplus w_L$ 的 MSB 仍然是 $d_P$（因为 $w_L$ 的最高位是 0，不会影响 $w_P$ 的最高位 1）。
   这意味着，如果玩家史莱姆的 MSB 位置为 $d$，它可以连续吃掉所有左边邻居中 MSB 位置小于 $d$ 的史莱姆，并且在这个过程中，玩家史莱姆的 MSB 始终保持在 $d$。

4. 预计算加速:
   基于上述观察，我们可以预计算一些信息来加速模拟。我们从左到右处理原始数组 $w$。

   • left[i][d]: 存储索引 $k \le i$ 中，满足 $w_k$ 的 MSB 位置 小于等于 $d$ 的最靠右的那个史莱姆的索引 $k$。
   • pre[i][j]: 存储前缀 $w_0, \dots, w_i$ 中，所有满足 MSB 位置 严格小于 $j$ 的史莱姆体重的 异或和。

   如何计算 left 和 pre (使用 0-based 索引):
   初始化 left[-1][d] = -1，pre[-1][j] = 0。
   对于 i 从 0 到 $n-1$：
   * left[i] = left[i-1] (继承)
   * pre[i] = pre[i-1] (继承)
   * 令 $d_i = \lfloor \log_2 w_i \rfloor$ (MSB 位置)。
   * 更新 left: 对于 $d$ 从 0 到 $d_i$，设置 left[i][d] = i。这意味着对于这些 $d$，现在最右边的 MSB $\le d$ 的史莱姆就是 $i$。对于 $d > d_i$ 的部分，left[i][d] 保持 left[i-1][d] 不变。
   * 更新 pre: 对于 $j$ 从 $d_i + 1$ 到 29 (或最大可能的位 30)，pre[i][j] = pre[i][j] \oplus w_i。这意味着 $w_i$ (其 MSB 是 $d_i$) 贡献给了所有 $j$ 值大于 $d_i$ 的前缀异或和。

5. 查询过程优化:
   对于一个查询 $x$，我们模拟玩家史莱姆从右向左吃的过程。设玩家史莱姆当前体重为 cur_x (初始为 $x$)，当前考虑的左邻居是索引 j (初始为 $n-1$)。

   • 循环: 当 cur_x > 0 且 j >= 0 时：
     1. 计算 cur_x 的 MSB 位置 $d = \lfloor \log_2 \text{cur\_x} \rfloor$。
     2. 快速跳跃: 找到最右边的索引 $k = \text{left}[j][d]$。这个 $k$ 是索引 $\le j$ 中，满足 $w_k$ 的 MSB $\le d$ 的最右位置。所有在 $k+1$ 到 $j$ 之间的史莱姆 $w_p$ 必定满足 MSB$(w_p) > d$。因此，玩家史莱姆（体重 cur_x，MSB 为 $d$）一定比这些 $w_p$ 要小，不可能吃掉它们。所以，玩家史莱姆最多能吃到索引 $k$ 的位置。
     3. 批量处理 (MSB < d): 在跳到 $k$ 之前，我们需要考虑 $0$ 到 $j$ 范围内所有 MSB $< d$ 的史莱姆。玩家史莱姆一定比它们大，可以吃掉它们。我们直接计算这些史莱姆对玩家体重的影响。它们的异或和可以通过 pre 数组得到：xor_sum_less_than_d = pre[j][d] ^ pre[k][d] （理论上是这样，但代码中直接用了 pre[j][d])。我们将玩家体重更新为 cur_x = cur_x ^ pre[j][d]。为什么代码用 pre[j][d] 而不是差分？ 因为 pre[j][d] 包含了所有 $p \le j$ 且 MSB$(w_p) < d$ 的异或和。这等价于假设我们把所有这些能吃的“小”史莱姆一次性吃掉后的体重。
     4. 更新位置: 将当前位置移动到 $j = k$。
     5. 检查边界: 如果 $j = -1$，说明已经吃到了最左边或跳过了所有，结束循环。
     6. 检查当前 $w_j$: 现在玩家史莱姆（体重为更新后的 cur_x）位于索引 $j+1$，左邻居是 $w_j$。检查是否能吃 $w_j$：if (cur_x < w[j])，如果不能吃，结束循环。
     7. 吃掉 $w_j$: 如果能吃，更新体重 cur_x = cur_x ^ w[j]。
     8. 移动: 准备检查下一个左邻居，j--。
   • 计算得分: 循环结束后，玩家史莱姆最终停在索引 j+1 的位置。它吃掉了原始索引从 j+1 到 $n-1$ 的所有史莱姆。吃掉的数量是 $(n-1) - (j+1) + 1 = n - 1 - j$。

6. 复杂度分析:

   • 预计算 left 和 pre 数组需要 $O(N \log W)$ 时间，其中 $W$ 是最大体重 (约为 $2^{30}$，所以 $\log W \approx 30$)。
   • 对于每次查询，while 循环的迭代次数是多少？在每次迭代中，要么 $j$ 减 1，要么通过 j = k 跳跃。可以证明，每次迭代要么 $j$ 减少，要么 cur_x 的 MSB 位置 $d$ 减小（当 cur_x 和 $w_j$ 的 MSB 相同并发生 XOR 抵消时）。$j$ 最多减少 $N$ 次，MSB 最多减少 $\log W$ 次。因此，每次查询的时间复杂度是 $O(\log W)$ 级别（或者更宽松地认为是 $O(N)$ 总步数分摊到 $Q$ 个查询和 $\log W$ 个位上，趋近于 $O(\log W)$）。
   • 总时间复杂度为 $O((N+Q)\log W)$。

时间复杂度

$O((N+Q)\log W)$

空间复杂度

$O(N \log W)$ 用于存储预计算的 left 和 pre 数组。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

// 解决单个测试用例的函数
void solve() {
    int n, q; // 初始史莱姆数量 n, 查询次数 q
    std::cin >> n >> q;

    std::vector<int> w(n); // 存储初始史莱姆的体重 (0-based index)
    for (int i = 0; i < n; i++) {
        std::cin >> w[i];
    }

    // left[i][d]: 索引 k <= i 中，满足 w[k] 的 MSB <= d 的最右索引 k。
    std::vector<std::array<int, 30>> left(n);
    // pre[i][j]: 前缀 w[0...i] 中，所有满足 MSB < j 的 w[k] 的异或和。
    std::vector<std::array<int, 30>> pre(n);

    // 预计算 left 和 pre 数组
    for (int i = 0; i < n; i++) {
        if (i) { // 继承前一个位置的信息
            left[i] = left[i - 1];
            pre[i] = pre[i - 1];
        } else { // i = 0 的初始化
            left[i].fill(-1); // 初始时左边没有满足条件的，设为 -1
            // pre[0] 初始应为 0，默认初始化即可
        }

        // 如果 w[i] 为 0 会出错，但题目保证 w_i >= 1
        int d = std::__lg(w[i]); // 计算 w[i] 的最高有效位 (MSB) 的位置 (0-based)
                                 // std::__lg(x) 返回 floor(log2(x))

        // 更新 left 数组
        // 对于所有位 d' <= d，现在最右满足 MSB <= d' 的索引是 i
        for (int j = 0; j <= d; j++) {
            left[i][j] = i;
        }
        // 对于所有位 d' > d, left[i][d'] 保持继承自 left[i-1][d']

        // 更新 pre 数组
        // w[i] 的 MSB 是 d。它贡献给所有 j > d 的前缀异或和。
        for (int j = d + 1; j < 30; j++) {
            pre[i][j] ^= w[i];
        }
    }

    // 处理 q 次查询
    for (int i = 0; i < q; i++) {
        int x; // 查询的初始体重
        std::cin >> x;

        int j = n - 1; // 玩家史莱姆当前左侧邻居的索引 (初始为 n-1)
        int current_x = x; // 玩家史莱姆的当前体重

        // 模拟吃的过程，从右向左
        while (current_x > 0 && j >= 0) {
            // d: 当前玩家体重的 MSB 位置
            int d = std::__lg(current_x); 
            // k: 索引 <= j 中，满足 MSB(w[k]) <= d 的最右索引
            int k = left[j][d];

            // 批量 XOR 更新：假设吃掉了所有索引 p (k < p <= j) 且 MSB(w[p]) < d 的史莱姆
            // (实际上代码用 pre[j][d] 包含了所有 p <= j 且 MSB < d 的)
            current_x ^= pre[j][d]; 

            // 跳跃到位置 k
            j = k; 

            // 如果跳到了边界之外，结束
            if (j == -1) {
                break;
            }

            // 检查是否能吃掉索引 j 处的史莱姆 w[j]
            // (此时 current_x 是批量 XOR 之后的值)
            if (current_x < w[j]) {
                break; // 不能吃，停止
            }

            // 能吃，更新体重
            current_x ^= w[j];

            // 移动到下一个位置
            j--; 
        }

        // 循环结束后，玩家史莱姆停在索引 j+1 的位置
        // 吃掉的史莱姆是从 j+1 到 n-1
        // 数量为 (n-1) - (j+1) + 1 = n - 1 - j
        std::cout << n - 1 - j << " \n"[i == q - 1]; // 输出得分，并处理行尾空格/换行
    }
}

// 主函数
int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve(); // 调用解决函数
    }

    return 0; // 程序正常结束
}