Official
E - Many Operations Editorial by kyopro_friends
操作は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;
}
posted:
last update: