rt

思路大概就是先把 $1$ $0$ 的影响去掉 就是 swap 一下 $a$ 数组

然后就是每个加进来，分类讨论

当前的是左节点就判断能不能赢 然后判断右节点是否存在，根据输赢情况进行选手的淘汰，然后往上递推

当前是右节点就判断能不能继续往上了递推

因为每个节点最多访问 $1$ 次（见代码） 所以时间复杂度是 $O(Tn + n \log_2 n)$

有大佬帮忙看看哪里打错了吗，或者说这个思路假了。。。

拜谢大佬！！蒟蒻感激不尽

#include <cstdio>
#include <cstring>
#ifndef ONLINE_JUDGE
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 657892
#endif

const int N = 100005, M = 1 << 17;
int _a[N], a[N], c[N], k;
int id[M + 5], idx[M + 5]; // 树中的i在a_i中的位置 a_i在树中的位置
unsigned long long ans[N], tr[M << 1];
bool vis[M << 1];
char s[M + 5];

inline long long get(const int& u) {
    vis[u] = true;
    if (u >= (1 << k)) return id[u - (1 << k) + 1];
    if (!tr[u]) {
        if (!vis[u << 1]) {
            tr[u] += get(u << 1);
            debug("Going to delete %llu...\n", tr[u << 1]);
        }
        if (!vis[u << 1 | 1]) {
            tr[u] += get(u << 1 | 1);
            debug("Going to delete %llu...\n", tr[u << 1 | 1]);
        }
    }
    return tr[u];
}
int main() {
    // freopen("arena/arena2.in", "r", stdin);
    int n, m, t, x[4];
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &_a[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d", &c[i]);
    for (k = 0; (1 << k) < n; ++k);
    for (int i = 1; i <= (1 << k); i++)
        id[i] = i;

    /// @brief 交换 `id [i,i+l),[i+l,i+2l)`
    static const auto swap = [] (int i, int l) {
        for (int j = i + l; l--; ++i, ++j)
            id[i] ^= id[j] ^= id[i] ^= id[j];
    };
    // 预处理 a 去掉 0、1 的影响
    for (int r = 1; r <= k; r++) {
        scanf("%s", s);
        for (int g = 0, i = 1; s[g]; ++g, i += 1 << r)
            if (s[g] ^ '0') swap(i, 1 << r-1);
    }
    for (int i = 1; i <= (1 << k); i++)
        idx[id[i]] = i;

    scanf("%d", &t);
    while (t--) {
        memset(tr, 0, (1 << k + 1) << 3);
        memset(vis, 0, 1 << k + 1);
        scanf("%d%d%d%d", &x[0], &x[1], &x[2], &x[3]);
        for (int i = 1; i <= n; i++)
            a[i] = _a[i] ^ x[i & 3];

        // 预处理 ans 做到 O(1) 询问
        unsigned long long sum = 1, del = 0;
        int cur = 0, u;
        for (int i = 1; i <= n; i++) {
            u = idx[i] + (1 << k) - 1;
            tr[u] = i;
            for (int r = 1; !vis[u] && r <= cur; r++, u >>= 1) {
                if (u & 1) {   // 右边的 (R)
                    if (tr[u - 1] && a[tr[u - 1]] < r) { // L 存在 并且输了
                        tr[u >> 1] = tr[u];         // 父节点是 R
                    }
                    else if (tr[u - 1] && a[tr[u - 1]] >= r)
                        tr[u >> 1] = tr[u - 1];
                    else break;                     // 待定
                }
                else {          // 左边的 (L)
                    if (a[tr[u]] >= r) {            // L 赢了
                        tr[u >> 1] = tr[u];         // 父节点是 L
                        del += get(u + 1);          // 删除 R
                        debug("Deleted! %llu\n", tr[u + 1]);
                    }
                    else {                          // R 赢了
                        del += tr[u];               // 删除 L
                        vis[u] = true;
                        debug("Deleted %llu\n", tr[u]);
                        if (tr[u + 1])
                            tr[u >> 1] = tr[u + 1]; // 父节点是 R
                        else break;
                    }
                }
                vis[u] = true;
            }
            ans[i] = sum - del;
            debug("%d: %llu %d %llu [%llu]\n", i, sum, cur, del, ans[i]);
            if ((1 << cur) == i) {  // sum 加上 i+1 + ... + 2^{++cur}
                u = 1 << (k - cur);             // 左边的 (L)
                if (tr[u]) {    // 若最顶端节点被更新了，则扩展到上面一层
                    if (a[tr[u]] >= cur) {          // L 赢了
                        tr[u >> 1] = tr[u];         // 父节点是 L
                        del += get(u + 1);          // 删除 R
                        debug("Deleted! %llu\n", tr[u + 1]);
                    }
                    else {                          // R 赢了
                        del += tr[u];               // 删除 L
                        vis[u] = true;
                        debug("Deleted %llu\n", tr[u]);
                    }
                }
                ++cur;
                sum += (i + 1llu + (1 << cur)) * ((1 << cur) - i) >> 1;
            }
        }

        unsigned long long res = 0;
        for (int i = 1; i <= m; i++)
            res ^= (unsigned long long)i * ans[c[i]];
        printf("%llu\n", res);
    }
    return 0;
}