Codeforces #532 Div2 F. Ivan and Burgers

意外に解いてる人多いな。
https://codeforces.com/contest/1100/problem/F

問題

整数列Cが与えられる。
以下のクエリに答えよ。
区間[L,R]が与えられる。C[L...R]のsubsetのうち、xorを取ったものの最大値を求めよ。

解法

分割統治法の要領で、探索空間を半々に絞りつつ解く。
今、探索空間C[S...U]とし、SとUの平均値をTとしたときに、S≦L≦T≦R≦Uであるクエリ[L,R]について解くことにしよう。
まず、S[T]から順にインクリメントしてS[U]まで要素を追加していくとき、順に基底となるbitvectorとして何が追加されていくかを求めていこう。
S[T...T']までからなる基底bitvectorの集合をBとしたとき、今bitvector S[T'+1]を追加するときに新規に追加されるbitvectorは何になるか、という話だが、v=S[T'+1]から始め、b∈Bに対しv=min(v,v^b)を繰り返すと、最終的に新規基底bitvectorが残る。

よって元のクエリに対し、S[T...R]の基底bitvectorが求められる。
同様にTの手前、S[T'...(T-1)]を徐々に手前に伸ばしていく際の基底bitvectorを求めることで、S[L..(T-1)]の基底bitvectorを求めよう。
あとはS[L...(T-1)]およびS[T...R]の規定bitvectorの集合から、xorの最大値を取ればよい。

int N;
int C[505050];
int Q;
int L[505050],R[505050],ret[505050];
vector<int> P[505050];

vector<int>& add(vector<int>& T,int v) {
	FORR(t,T) v=min(v,t^v);
	if(v) T.push_back(v);
	//sort(ALL(T)); reverse(ALL(T));
	return T;
	
}

void dfs(int le,int ri,vector<int>& V) {
	if(V.empty()) return;
	if(le+1==ri) {
		FORR(c,V) ret[c]=C[le];
		return;
	}
	int mi=(ri+le)/2;
	vector<int> A[3];
	FORR(v,V) {
		if(R[v]<=mi) A[0].push_back(v);
		else if(L[v]>=mi) A[1].push_back(v);
		else A[2].push_back(v);
	}
	
	if(A[2].size()) {
		vector<int> T,T2;
		int i;
		for(int i=mi;i<ri;i++) P[i]=add(T,C[i]);
		T.clear();
		for(int i=mi-1;i>=le;i--) P[i]=add(T,C[i]);
		FORR(v,A[2]) {
			T=P[L[v]];
			FORR(x,P[R[v]-1]) add(T,x);
			FORR(t,T) ret[v]=max({ret[v]^t,ret[v]});
		}
	}
	dfs(le,mi,A[0]);
	dfs(mi,ri,A[1]);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	scanf("%d",&N);
	FOR(i,N) scanf("%d",&C[i]);
	scanf("%d",&Q);
	vector<int> V;
	FOR(i,Q) {
		scanf("%d%d",&L[i],&R[i]);
		L[i]--;
		V.push_back(i);
	}
	dfs(0,N,V);
	
	FOR(i,Q) cout<<ret[i]<<endl;
	
	
}

まとめ

新規にbitvectorを追加したときの規定vectorの求め方が参考になった。