题解：P11160 【MX-X6-T6】機械生命体

Loyal_Soldier · 2026-08-10 18:02:41 · 题解

思路

如果你不会 01Trie 全局加 1 全局异或和，欢迎看我的这篇题解。

首先从低位到高位建 01Trie。

操作一和操作二是简单的。

对于操作三，就是沿 x 二进制位从低到高走 k 位然后进行一个子树加；对于操作四，沿着 x 二进制位从低到高走直到子树为空为止。

由于只有子树加和判断当前子树是否为空，维护子树大小即可。

子树加 v 看起来不好做，考虑全局加 v 怎么做。

如果 v 是偶数，打上一个 v 的标记，下传就给左右子树打上 \frac{v}{2} 的标记；如果 v 是奇数，拆成全局加 1 和全局加 v - 1，但是这里全局加 1 需要先把标记打到右子树，然后再交换，否则会变成 \log ^2。

对于子树加，我们考虑将这棵子树分裂出来进行全局加，然后再合并回去，如果你不会 Trie 树合并，可以先做这题。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 3e5 + 10;
const int MAXM = 3e7 + 10;
const int MAXH = 31;
int n;
int ch[MAXM][2], siz[MAXM], lzy[MAXM];
int cnt, root;
void pushup(int u) {
    if (!u) return;
    siz[u] = siz[ch[u][0]] + siz[ch[u][1]];
} 
void pushdown(int u) {
    if (!u) return; 
    if (lzy[u] & 1) {
        swap(ch[u][1], ch[u][0]);
        if (ch[u][0]) lzy[ch[u][0]]++;
        lzy[u]--;
    }
    if (ch[u][0]) lzy[ch[u][0]] += lzy[u] / 2;
    if (ch[u][1]) lzy[ch[u][1]] += lzy[u] / 2;
    lzy[u] = 0;
}
void insert(int &u, int x, int dep) {
    if (!u) u = ++cnt;
    if (dep > MAXH) {
        siz[u]++;
        return;
    }
    pushdown(u);
    insert(ch[u][x & 1], x >> 1, dep + 1);
    pushup(u);
}
void erase(int &u, int x, int dep) {
    if (!u) u = ++cnt;
    if (dep > MAXH) {
        siz[u]--;
        return;
    }
    pushdown(u);
    erase(ch[u][x & 1], x >> 1, dep + 1);
    pushup(u);
}
void merge(int &u, int v, int dep) {
    if (!u || !v) {
        u += v;
        return;
    }
    if (dep > MAXH) {
        siz[u] += siz[v];
        return;
    }
    pushdown(u), pushdown(v);
    merge(ch[u][0], ch[v][0], dep + 1);
    merge(ch[u][1], ch[v][1], dep + 1);
    pushup(u);
}
void split(int &u, int &v, int x, int dep, int k) {
    if (!u) return;
    if (dep == k) {
        v = u, u = 0;
        return;
    }
    if (!v) v = ++cnt;
    pushdown(u);
    split(ch[u][x & 1], ch[v][x & 1], x >> 1, dep + 1, k);
    pushup(u), pushup(v);
}
int query(int u, int x, int dep) {
    pushdown(u);
    if (dep > MAXH) return 32;
    if (!siz[ch[u][x & 1]]) return dep;
    return query(ch[u][x & 1], x >> 1, dep + 1);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    while (n--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) insert(root, x, 0);
        else if (op == 2) erase(root, x, 0);
        else if (op == 3) {
            int k, v;
            cin >> k >> v;
            int qwq = 0;
            split(root, qwq, x, 0, k);
            if (qwq) lzy[qwq] += v;
            merge(root, qwq, 0);
        } else cout << (1ll << query(root, x, 0)) << '\n';
    }
    return 0;
}