官方题解｜宏量运算

题目解析

对于位运算而言，每一「位」的计算结果都是 相互独立 的，而每次运算后的结果只有 $0$ 和 $1$ 两种可能的结果，所以我们可以单独考虑运算对每一位的影响。

• 令 $one_i$ 为：前 $i$ 个运算对 $X$ 中二进制位上的 $1$ 产生影响后的结果。

• 令 $zero_i$ 为：前 $i$ 个运算对 $X$ 中二进制位上的 $0$ 产生影响后的结果。

那么对于当前 $X$ 施加前 $i$ 个运算的影响的结果，应为：

• 将当前的 $X$ 二进制位上的 $1$ 转化为 $one_i$ 对应二进制位上的状态，位运算操作为 $(X\ \mathrm{and}\ one_i)$；
• 将当前 $X$ 二进制位上的 $0$ 转化为 $zero_i$ 对应二进制位上的状态，位运算的操作为 $((X \ \mathrm{xor}\ M) \ \mathrm{and}\ zero_i)$，其中 $M = 2^{30} - 1$（即有效二进制位上全为 $1$）；

如何维护 $one_i$ 和 $zero_i$ ？

很简单，只需要在每次操作时，将对 $X$ 执行的位运算作用到 $one_i$ 和 $zero_i$ 上即可。

每次位运算的时间复杂度为 $\mathrm{O}(1)$，总的时间复杂度为 $\mathrm{O}(N)$。

AC代码

C++ 代码：

#include <bits/stdc++.h>

constexpr int N = 30;
constexpr int M = (1 << 30) - 1;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, c;
    std::cin >> n >> c;
    int one = M, zero = 0, x = c;
    for (int i = 0; i < n; ++i) {
        int t, a;
        std::cin >> t >> a;
        if (t == 1)
            one &= a, zero &= a;
        else if (t == 2)
            one |= a, zero |= a;
        else
            one ^= a, zero ^= a;
        x = (x & one) | ((M ^ x) & zero);
        std::cout << x << '\n';
    }
    return 0;
}

Python 代码：

N = 30
M = (1 << N) - 1
n, c = map(int, input().split())
one, zero, x = M, 0, c
for i in range(n):
    t, a = map(int, input().split())
    if t == 1:
        one, zero = one & a, zero & a
    elif t == 2:
        one, zero = one | a, zero | a
    else:
        one, zero = one ^ a, zero ^ a
    x = (x & one) | ((M ^ x) & zero)
    print(x)