思路与算法

能力只会与轮数 $1\ldots K$ 比较，故把能力截到 $K=\lceil\log_2n\rceil$。每组先计算完全已知子树的唯一胜者。对报名前缀 $c$，其比赛根取最小包含 $c$ 的左端完整块 $[1,2^k]$，右侧选手未知。

一个部分已知子树有两类可能冠军：已知候选有固定能力；未知候选可在任意更高轮选择低于轮数或足够大的能力。后者成立是因为它此前所有主场胜利要求的能力下界至多为当前轮数。如果没有未知候选，整场结果就退化为唯一已知胜者。

不要对每个前缀逐层复制候选集合。把上层比赛合成为上下文。对于包含未知候选的子树，上层答案总可写成“未知候选编号和 + 能力至少 $H$ 的已知候选编号和 + 常数 $C$”。对于确定冠军 $w$，上下文是能力分桶函数 $F(a_w,w)=\mu(a_w)w+\beta(a_w)$。

递归向左孩子时，右孩子全部未知，其可能冠军是全部右侧编号，和为等差数列。左为擂主时，仅低于本轮 $R$ 的能力桶被改成常数，未知上下文阈值收紧到 $\max(H,R)$；右为擂主时，确定冠军函数整体重置为一个阈值阶梯。递归向右孩子时，左孩子胜者 $w$ 已知：若左为擂主且能力足够，整段前缀答案直接固定；若其能力不足则透传右子树；若右为擂主，则把低于 $R$ 的桶改为 $F(a_w,w)$，并在未知上下文中按 $a_w\ge H$ 决定是否加上 $w$。

桶的整函数重置用版本戳，低能力前缀常数赋值保存旧值后回滚。遍历到叶 $c$，用上下文计算该前缀答案。分别处理各个 $k$ 的右半前缀，避免把不足的报名人数扩充到过大的2次幂。最后按询问编号乘法异或。

正确性说明

完全已知子树的胜者由比赛规则唯一确定，底向上预处理显然正确。对于未知选手，成为当前子树冠军所需的自身能力只包含若干“至少为某一已进行轮数”的下界；不作为擂主时，能否获胜由另一侧决定，不会添加自身上界。因此该未知冠军在下一轮既能取小于新轮数的能力而作为擂主落败，也能取足够大能力而获胜。

据此逐种检查左右擂主即可得到算法中的上下文变换：未知擂主可输可赢，所以非擂主候选可保留；已知擂主只在能力达标时保留自己，否则保留另一侧。包含未知候选的状态在线性过滤式下闭合，而确定胜者函数只发生能力前缀常数覆盖或整体阈值重置。所有变换都逐一对应真实比赛的可能胜者集合，编号和恰好相加，没有把同一已知编号从两侧重复加入。根上下文是恒等计和函数，递归到确定叶时于是给出该前缀全部可能冠军编号和。最小2次幂分组和最后的指定异或完全按题意执行。

复杂度

输入及完整树、数组初始化为 $O(n+m+T)$ 时间，空间 $O(n+m)$。每组胜者树为 $O(n)$；各最小2次幂根覆盖的树节点总数 $O(n)$。轮数为 $R$ 的节点只修改 $R$ 个低能力桶，同一完整树上总修改量为 $\sum_R O(R\,n/2^R)=O(n)$；版本重置为 $O(1)$，回滚等量。被固定的前缀区间互不重叠，其填写也共 $O(n)$。每组计算与询问汇总为 $O(n+m)$，全部 $T$ 组为 $O(T(n+m))$，额外空间 $O(n+m+K^2)=O(n+m)$。

易错点

每个询问扩充到自己的最小2次幂，而非统一到输入的总人数上界。补充选手也要计入编号和。能力异或的下标是1开始的 $i\bmod4$。未知冠军在更高轮可取低能力的事实依赖轮数严格递增，不可把“未知”替成固定大能力。版本重置后旧桶不可泄漏，递归返回必须回滚。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Solver {
    int n, m, N, K, serial, lower, upper;
    vector<int> original, query, ability, winner, orientation;
    vector<ll> answer;
    int stamp[32];
    ll replacement[32];
    struct Context {
        int version, threshold;
        ll constant;
    };
    ll eval(Context ctx, int person) {
        int a = ability[person];
        if (a < K && stamp[a] == ctx.version)
            return replacement[a];
        return ctx.constant + (a >= ctx.threshold ? person : 0);
    }
    void assigned(int child, int l, int r, int round, Context ctx, int H, ll C, ll value,
                  int count) {
        int oldStamp[32];
        ll oldValue[32];
        for (int a = 0; a < count; a++) {
            oldStamp[a] = stamp[a];
            oldValue[a] = replacement[a];
            stamp[a] = ctx.version;
            replacement[a] = value;
        }
        dfs(child, l, r, round, ctx, H, C);
        for (int a = 0; a < count; a++) {
            stamp[a] = oldStamp[a];
            replacement[a] = oldValue[a];
        }
    }
    void dfs(int node, int l, int r, int round, Context ctx, int H, ll C) {
        if (l > upper || r < lower)
            return;
        if (l == r) {
            answer[l] = eval(ctx, l);
            return;
        }
        int mid = (l + r) / 2, host = orientation[node];
        if (l <= upper && mid >= lower) {
            ll U = (ll)(mid + 1 + r) * (r - mid) / 2;
            if (host == 0)
                assigned(node * 2, l, mid, round - 1, ctx, max(H, round), C + U, C + U, round);
            else {
                Context next = {++serial, H, C + U};
                dfs(node * 2, l, mid, round - 1, next, H, C + U);
            }
        }
        if (mid + 1 <= upper && r >= lower) {
            int w = winner[node * 2];
            if (host == 0) {
                if (ability[w] >= round) {
                    ll value = eval(ctx, w);
                    for (int i = max(mid + 1, lower); i <= min(r, upper); i++)
                        answer[i] = value;
                } else
                    dfs(node * 2 + 1, mid + 1, r, round - 1, ctx, H, C);
            } else {
                ll value = eval(ctx, w);
                assigned(node * 2 + 1, mid + 1, r, round - 1, ctx, max(H, round),
                         C + (ability[w] >= H ? w : 0), value, round);
            }
        }
    }
    void execute(const int X[4]) {
        for (int i = 1; i <= N; i++)
            ability[i] = i <= n ? min(K, original[i] ^ X[i % 4]) : 0;
        for (int i = 1; i <= N; i++)
            winner[N + i - 1] = i;
        for (int R = 1; R <= K; R++)
            for (int node = N >> R; node < (N >> (R - 1)); node++) {
                int host = node * 2 + orientation[node], other = node * 2 + (orientation[node] ^ 1);
                winner[node] = ability[winner[host]] >= R ? winner[host] : winner[other];
            }
        fill(stamp, stamp + 32, 0);
        serial = 1;
        answer[1] = 1;
        for (int k = 1; k <= K; k++) {
            lower = (1 << (k - 1)) + 1;
            upper = min(n, 1 << k);
            if (lower > upper)
                continue;
            Context ctx = {++serial, 0, 0};
            dfs(N >> k, 1, 1 << k, k, ctx, 0, 0);
        }
        ll sum = 0;
        for (int i = 1; i <= m; i++)
            sum ^= (ll)i * answer[query[i]];
        cout << sum << '\n';
    }
    void run() {
        cin >> n >> m;
        N = 1;
        K = 0;
        while (N < n)
            N *= 2, ++K;
        original.resize(n + 1);
        query.resize(m + 1);
        ability.resize(N + 1);
        winner.resize(2 * N);
        orientation.resize(N);
        answer.resize(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> original[i];
        for (int i = 1; i <= m; i++)
            cin >> query[i];
        for (int R = 1; R <= K; R++) {
            string s;
            cin >> s;
            for (int G = 0; G < (N >> R); G++)
                orientation[(N >> R) + G] = s[G] - '0';
        }
        int T;
        cin >> T;
        while (T--) {
            int X[4];
            for (int &x : X)
                cin >> x;
            execute(X);
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solver().run();
}