think-cell Round 1 : F. Maximize the Difference

本番中には解けず…。
https://codeforces.com/contest/1930/problem/F

問題

整数列bに対し、f(b)を非負整数xを任意の選んだ時の max(b[i]|x) - min(b[i]|x) の最大値とする。
空の整数列aに対し、N以下の値を追加するクエリが与えられるのでその都度f(a)を求めよ。

解法

f(b)の最大値は、(B[i] & ~B[j])の最大値となる
S1を、B[i]をbit集合とみなしたときのB[i]の部分集合に相当する値の集合で、S2を~B[i]の部分集合に相当する値の集合とする。
S1とS2の共通部分の最大値が解となる。
よって、aに要素が増えるたび、BFSの要領でS1・S2に対応する値を追加していこう。

int T,N,Q;
vector<int> V;
int vis[2][1<<22];

int ret;

void add(int v,int id) {
	if(vis[id][v]) return;
	queue<int> Q;
	vis[id][v]=1;
	Q.push(v);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		if(vis[0][cur]&&vis[1][cur]) ret=max(ret,cur);
		int i;
		FOR(i,22) if(cur&(1<<i)) {
			int ncur=cur^(1<<i);
			if(vis[id][ncur]==0) {
				vis[id][ncur]=1;
				Q.push(ncur);
			}
		}
		
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		int M=1,L=0;
		while(M<N) M*=2,L++;
		FOR(i,M) vis[0][i]=vis[1][i]=0;
		
		ret=0;
		while(Q--) {
			cin>>x;
			x=(x+ret)%N;
			add(x,0);
			add(x^(M-1),1);
			cout<<ret<<" ";
		}
		cout<<endl;
		
		
	}
}

まとめ

コードは余り長くないんだよな。