T27:Eating

1）题目意思

有一排 n 个史莱姆，体重是 w1..wn。

现在对每个询问给一个 x：在最右边追加一个体重为 x 的新史莱姆，它会不断尝试吃掉左侧相邻史莱姆：

• 若当前体重 cur >= 左边史莱姆体重 w，则吃掉它，cur 变成 cur XOR w，并向左移动一格
• 否则停止

这一过程只影响新史莱姆，不会让原来的史莱姆互相吃。

你要输出：新史莱姆最终能吃掉多少个史莱姆。

多组测试，所有测试的 n 总和与 q 总和都不超过 2e5。

---

2）思路解析（对应你给的“msb + 跳跃 + 前缀xor”的做法，保证可过大数据）

关键结论 1：如果某个史莱姆的 msb 比当前 x 小，一定能吃掉

设 msb(v) 是 v 的最高位位置（例如 msb(1)=0, msb(2)=1, msb(3)=1, msb(4)=2）。

若 msb(w) < msb(x)，那么一定有 w < 2^{msb(x)} <= x，所以当前 x >= w，必然能吃。

关键结论 2：吃掉 msb 更小的史莱姆，不会让 msb(x) 变小

当 msb(w) < msb(x) 时，x XOR w 的最高位仍然保持在 msb(x)（不会被更低位的数改变掉最高位）。

所以：在 msb(x) 固定不变时，我们可以“批量吃掉一段 msb 更小的史莱姆”，只要能快速算出这段的 xor。

关键结论 3：只有吃掉“msb 相等”的史莱姆，msb(x) 才可能下降

当 msb(w) == msb(x) 且能吃掉时（x >= w），吃完变成 x XOR w，最高位那一位会被消掉，msb(x) 会下降到更小。

因此：msb(x) 每次真正“跨过一个障碍”都会下降，最多下降 30 次（因为数 < 2^30）。

如何快速找到“左边最近一个 msb >= 当前 msb(x) 的位置”

预处理数组 last[i][b]：

• 表示在下标 0..i 范围内，最后一个满足 msb(w[pos]) >= b 的位置 pos
• 如果不存在则为 -1

这样对于当前指针 idx 和当前 msb(x)=b，下一次需要处理的“关键位置”就是：

• nxt = last[idx][b]

在 (nxt+1 .. idx) 这一段中，所有史莱姆都满足 msb < b，所以它们都必吃，可以用前缀 xor 一次性算掉。

如何快速算区间 xor

预处理前缀异或 px[i] = w0 XOR w1 XOR ... XOR w(i-1)（长度 n+1）：

• 区间 (l..r) 的 xor = px[r+1] XOR px[l]

这样“批量吃掉 (nxt+1..idx)”后：

• x ^= (xor of w[nxt+1..idx])
• 然后尝试吃 w[nxt]（若 x >= w[nxt] 则吃掉并 x ^= w[nxt]，继续往左）

整个查询循环次数最多 O(log W) 次（大约 30 次），所以总复杂度 O((n+q)*logW)。

---

#include <bits/stdc++.h>
using namespace std;

const int W = 30;                                                     // 由于数值 < 2^30，最高位最多到29

int main(){                                                           // 主函数入口
    ios::sync_with_stdio(false);                                      // 加速输入输出
    cin.tie(nullptr);                                                 // 加速输入输出

    int t;                                                            // 测试用例数量
    cin >> t;                                                         // 读入t

    while(t--){                                                       // 循环处理每个测试用例
        int n,q;                                                      // n个史莱姆，q次询问
        cin >> n >> q;                                                // 读入n和q

        static int a[200005];                                         // 存体重数组（多测总和<=2e5）
        for(int i=0;i<n;i++) cin >> a[i];                             // 读入a

        static int px[200006];                                        // 前缀xor数组，px[0]=0
        px[0]=0;                                                      // 初始化前缀xor
        for(int i=0;i<n;i++) px[i+1]=px[i]^a[i];                      // px[i+1]=a[0]^...^a[i]

        static int last[200005][W];                                   // last[i][b]：0..i中最后一个msb>=b的位置
        for(int b=0;b<W;b++) last[0][b]=-1;                           // 先把last[0][*]设为-1

        for(int i=0;i<n;i++){                                         // 预处理last表
            if(i>0){                                                  // 如果不是第一位
                for(int b=0;b<W;b++) last[i][b]=last[i-1][b];         // 继承上一位置的last信息
            }else{                                                    // 如果是第一位
                for(int b=0;b<W;b++) last[i][b]=-1;                   // 第一位先全设为-1
            }

            int msb = 31 - __builtin_clz((unsigned)a[i]);             // 求a[i]的最高位位置（a[i]>=1）
            last[i][msb]=i;                                           // 对应msb位置更新为i

            for(int b=W-2;b>=0;b--){                                  // 把“msb>=b”的信息下传
                last[i][b]=max(last[i][b], last[i][b+1]);             // 只要有更高msb出现，也算满足msb>=b
            }
        }

        while(q--){                                                   // 处理每次询问
            int x;                                                    // 新史莱姆体重
            cin >> x;                                                 // 读入x

            int idx=n-1;                                              // idx表示当前在原数组中“紧贴左侧”的位置
            int eaten=0;                                              // 记录吃掉数量

            while(idx>=0 && x>0){                                     // 只要左边还有史莱姆且x>0就继续尝试
                int msb = 31 - __builtin_clz((unsigned)x);             // 当前x的最高位

                int nxt = last[idx][msb];                              // 找到0..idx中最后一个msb>=msb(x)的位置
                if(nxt==-1){                                          // 若不存在这样的史莱姆
                    int segxor = px[idx+1] ^ px[0];                    // 说明0..idx全部msb更小，都能吃
                    x ^= segxor;                                       // 批量xor更新x
                    eaten += (idx+1);                                  // 吃掉idx+1个
                    idx = -1;                                          // 左边已无史莱姆
                    break;                                             // 结束
                }

                if(nxt<idx){                                          // 先把(nxt+1..idx)这段msb更小的全部吃掉
                    int segxor = px[idx+1] ^ px[nxt+1];                // 这段的xor
                    x ^= segxor;                                       // 更新x
                    eaten += (idx - nxt);                              // 吃掉数量加上段长
                    idx = nxt;                                         // 现在紧贴的位置变成nxt
                }

                if(idx<0) break;                                       // 保险：若已经到头则退出

                if(a[idx] > x) break;                                  // 如果左边这个“关键史莱姆”比x大，则吃不了，停止

                x ^= a[idx];                                           // 吃掉a[idx]，x变为x xor a[idx]
                eaten += 1;                                            // 吃掉数量+1
                idx -= 1;                                              // 继续尝试更左边
            }

            cout << eaten << "\n";                                     // 输出本次询问答案
        }
    }

    return 0;                                                          // 程序结束
}