意外に解いてる人多いな。
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の求め方が参考になった。