[原题链接](https://atcoder.jp/contests/abc261/tasks/abc261_e "原题链接") ### 题意 一共n轮操作，每一次操作输入op和a: op == 1, x &= a; op == 2, x |= a; op == 3, x ^= a; 第i轮操作时操作，将进行1,2,3,...,i 次操作（前缀操作） 询问每一轮操作后的x值，x不断更新 ### 分析 位独立 + 要么0要么1 其实就是函数规则的复合  （类似"走地图"） 所以可以分别以0为起点/以1为起点，来迭代更新 ### 代码 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; typedef pair<int, int> pii; const int N = 2e5 + 5; int n, x; pii p[N]; signed main () { cin >> n >> x; int m = pow(2,30)-1; int s1 = m, s0 = 0; while (n --) { int op, y; cin >> op >> y; if (op == 1) s1 &= y, s0 &= y; else if (op == 2) s1 |= y, s0 |= y; else s1 ^= y, s0 ^= y; x = (x & s1) | ((x^m)&s0); cout << x << endl; } } //模拟该过程 ``` ### 思路1 如果把 看作一个数来处理并不是很好处理，我们把 变为二进制数，一位一位看。 还是考虑DP，我们设f{i, j, 0/1}表示执行完操作 1，2，，⋯，i，第 i 位原先是0/1 ，现在的状态。 于是可以就可以直接按照规则处理。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; int n, c, t[200005], a[200005], f[200005][35][2]; int pd(int t, int a, int b) { if (t == 1) return a & b; if (t == 2) return a | b; return a ^ b; } int main() { scanf("%d%d", &n, &c); for (int i = 1; i <= n; i++) scanf("%d%d", &t[i], &a[i]); for (int i = 1; i <= 31; i++) f[0][i][1] = 1; for (int i = 1, op; i <= n; i++) { op = a[i]; for (int j = 1; j <= 30; j++, op = op >> 1) { f[i][j][0] = pd(t[i], f[i - 1][j][0], op & 1); f[i][j][1] = pd(t[i], f[i - 1][j][1], op & 1); } } int ans = c, last; for (int i = 1; i <= n; i++) { last = ans, ans = 0; for (int j = 1; j <= 30; j++) if (f[i][j][(last >> (j - 1)) & 1]) ans += (1 << (j - 1)); printf("%d\n", ans); } return 0; } ``` ### 思路2 为了方便，称执行操作1,2⋯ 为第i轮操作 位运算问题，考虑按位计算。把C拆成每一位，求出他的运算后的答案。这是就只用考虑and,xor,or 0/1 - xor 0,and 1,or 0可以看作不变，不操作 - xor 1其实就是取反，可以打上取反标记。 - and 0=直接赋值为0，取反标记清空，答案直接为0，不管前面有哪些多少操作。 - or 1=直接赋值为1，同上 但是有很多轮操作，所以我们可以推出第i轮结束时赋值和取反操作情况。如果是没有赋值，那么第i轮结束后这一位答案就是上一轮结束答案^取反操作，否则就直接赋值。注意取反后赋值操作跟着取反。 每一位都这样操作，相加，就求出了答案。 ```cpp #include<cstdio> const int N=2e5+5; int n,c,ans[N],rt,tx,tt,t[N],a[N]; int main() { scanf("%d%d",&n,&c); for(int i=1;i<=n;i++) scanf("%d%d",t+i,a+i); for(int i=30;~i;i--) { tx=0,rt=-1,tt=c>>i&1;//rt:赋值,tx:取反 for(int j=1;j<=n;j++) { if(t[j]==1) if(!(a[j]&1<<i)) rt=tx=0; if(t[j]==2) if(a[j]&1<<i) rt=1,tx=0; if(t[j]==3) if(a[j]&1<<i) tx^=1; if(rt==-1) tt=tt^tx; else tt=rt^tx; ans[j]+=tt<<i; } } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); } ```