操作はbitごとに独立であるため、bitごとに分けて考えて良いです。

操作 \(i\) を \(\{0,1\}\) から \(\{0,1\}\) への関数 \(f_i\) とみなします。関数 \(f\) を組 \((f(0),f(1))\) で表現しながら、合成関数 \(f_i\circ f_{i-1}\circ\ldots \circ f_1\) を順に計算することで、この問題を \(O(N\log A)\) で解くことができます。

実装例(C++)

#include<bits/stdc++.h>
using namespace std;
#define bit(x,i)(((x)>>(i))&1)

int main(){
	int n,c;
	cin >> n >> c;
	vector<pair<int,int>>op(n);
	for(int i=0;i<n;i++)cin >> op[i].first >> op[i].second;

	vector<int>ans(n);
	for(int k=0;k<30;k++){
		array<int,2>func={0,1};
		int crr=bit(c,k);
		for(int i=0;i<n;i++){
			array<int,2>f;
			int x=bit(op[i].second,k);
			if(op[i].first==1)f={0&x,1&x};
			if(op[i].first==2)f={0|x,1|x};
			if(op[i].first==3)f={0^x,1^x};
			func={f[func[0]],f[func[1]]};
			crr=func[crr];
			ans[i]|=crr<<k;
		}
	}

	for(int i=0;i<n;i++)cout << ans[i] << endl;
}

類題 『Odd Operator』(MojaCoder)