试试使用OpenAI的DeepResearch解题

---

---

---

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = (1<<17) + 5;
static ll diff_arr[MAXN];
static int fc[2*MAXN], tc_[2*MAXN];
static int a_[MAXN];
static int n, m, Tc;
static char tmp[MAXN];
static int D[MAXN];
static int A_[MAXN], c_[MAXN];
static int K;

// dfs1: compute for each node x in tournament tree the champion index (tc_) and
// a threshold value (fc). Leaves (h=0) are players with abilities a_[idx].
void dfs1(int x, int h) {
    if (h == 0) {
        int idx = x - (1 << K) + 1;
        fc[x] = a_[idx];
        tc_[x] = idx;
        return;
    }
    dfs1(x<<1, h-1);
    dfs1(x<<1|1, h-1);
    if (!D[x] && fc[x<<1] >= h) {
        tc_[x] = tc_[x<<1];
    } else {
        tc_[x] = tc_[x<<1|1];
    }
    // Determine which subtree contributes champion ability
    int choose = (D[x] ^ (fc[x<<1] < h));
    fc[x] = fc[(x<<1) | choose];
}

// dfs2: traverse the subtree x with height h, given a minimum host ability hi and
// a range [L,R) of prefix sizes. Accumulate contributions to diff_arr for leaf indices.
void dfs2(int x, int hi, int h, int L, int R) {
    if (h == 0) {
        int v = x - (1 << K) + 1;
        if (L < min(R, v)) {
            diff_arr[L] += v;
            diff_arr[min(R, v)] -= v;
        }
        if (a_[v] >= hi && max(v, L) < R) {
            diff_arr[max(v, L)] += v;
            diff_arr[R] -= v;
        }
        return;
    }
    if (!D[x]) {
        dfs2(x<<1, max(hi, h), h-1, L, R);
        dfs2(x<<1|1, hi, h-1, L, (fc[x<<1] >= h ? min(R, tc_[x<<1]) : R));
    } else {
        dfs2(x<<1, hi, h-1, L, (fc[x<<1|1] >= h ? min(R, tc_[x<<1|1]) : R));
        dfs2(x<<1|1, max(hi, h), h-1, L, R);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> A_[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> c_[i];
    }
    // Compute smallest K such that 2^K >= n
    K = 0;
    while ((1 << K) < n) K++;
    // Read draw (D array) for each node of the tournament tree
    for (int d = K-1; d >= 0; d--) {
        cin >> tmp;
        for (int i = 0; i < (1 << d); i++) {
            D[i + (1<<d)] = tmp[i] - '0';
        }
    }
    // Number of test cases
    cin >> Tc;
    while (Tc--) {
        int X[4];
        cin >> X[0] >> X[1] >> X[2] >> X[3];
        // Compute actual abilities by XOR transform
        for (int i = 1; i <= n; i++) {
            a_[i] = A_[i] ^ X[i & 3];
        }
        // First DFS to compute fc and tc for each node
        dfs1(1, K);
        // Reset diff array
        for (int i = 0; i <= n; i++) {
            diff_arr[i] = 0;
        }
        // For each block of prefix sizes [L,R), do a DFS to accumulate possible champions
        for (int d = 0; d <= K; d++) {
            int x = 1 << (K - d);
            int L = (d == 0 ? 1 : (1 << (d-1)) + 1);
            int R = (1 << d) + 1;
            dfs2(x, 0, d, L, R);
        }
        // Build prefix sums to get answer for each prefix size
        for (int i = 1; i <= n; i++) {
            diff_arr[i] += diff_arr[i-1];
        }
        ll ans = 0;
        // Compute final XOR of i * A_i for queries
        for (int i = 1; i <= m; i++) {
            ans ^= (ll)i * diff_arr[c_[i]];
        }
        cout << ans;
        if (Tc) cout << "\n";
    }
    return 0;
}

结果：