AtCoder ABC #223 : H - Xor Query

細かいところ詰めるのにだいぶ手間取った。
https://atcoder.jp/contests/abc223/tasks/abc223_h

問題

整数列Aが与えられる。
以下のクエリに答えよ。

• 区間[L,R]と整数Xが与えられる。A[L]～A[R]の部分集合のうち、xorを取るとXとなるものは存在するかを答えよ。

解法

Aの各要素をbit vectorとみなす。
A[1]～A[R]からなる行列における基底ベクトルを求めておき、クエリ[L,R]に対し、A[L]～A[R]に含まれる基底ベクトルの合成でXが作れるかを判定しよう。
上記処理をRの小さい順に処理して行くとよい。

基底ベクトルを求める際、以下の2つに留意すること。

• 極力添え字の大きな要素を基底ベクトルに選んでおく
• 基底ベクトルはそのまま使うのではなく、それぞれ合成して各bitが高々1要素でしか立っていないような状態にしておく。また、元の基底ベクトルA[x]をどう組み合わせればそのような基底ベクトルが作れるかをbitmaskを用いて管理しておく。

bitmaskの処理がO(1)で行えるとすると、基底ベクトルの数が高々log(max(A))であることを考えるとRを平面走査する際の基底ベクトルの入れ替え処理はO(log(max(A))、Xを作れるかどうかの判定もO(log(max(A))で行える。

int N,Q;
vector<int> K;
ll mask[66];
ll A[404040],B[404040];
int ret[404040];
int L[404040],R[402020];
ll X[404040];
vector<int> ev[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	FOR(i,Q) {
		cin>>L[i]>>R[i]>>X[i];
		L[i]--;
		R[i]--;
		ev[R[i]].push_back(i);
	}
	FOR(i,N) {
		ll V=A[i];
		
		ll nm=0;
		FOR(j,K.size()) if((A[K[j]]^V)<V) {
			V=(A[K[j]]^V);
			nm^=mask[j];
		}
		
		if(V==0) {
			j=-1;
			FOR(x,K.size()) if(nm&(1LL<<x)) {
				if(j==-1) j=x;
				else if(K[j]>K[x]) j=x;
			}
			FOR(x,K.size()) if(mask[x]&(1LL<<j)) {
				swap(mask[x],mask[j]);
				swap(A[K[x]],A[K[j]]);
				break;
			}
			A[i]=A[K[j]];
			K[j]=i;
			FOR(x,K.size()) if(mask[x]&(1LL<<j)) {
				mask[x]^=nm;
				mask[x]^=1LL<<j;
			}
		}
		else {
			A[i]=V;
			K.push_back(i);
			j=K.size()-1;
			mask[j]=nm|(1LL<<j);
		}
		FOR(x,K.size()) if(x!=j) if(A[K[x]]>(A[K[x]]^V)) {
			A[K[x]]^=V;
			mask[x]^=mask[j];
		}
		
		FORR(e,ev[i]) {
			ll V=X[e];
			ll nm=0;
			FOR(j,K.size()) {
				if((A[K[j]]^V)<V) {
					V=(A[K[j]]^V);
					nm ^= mask[j];
				}
			}
			if(V==0) {
				int mi=1<<20;
				FOR(j,K.size()) if(nm&(1LL<<j)) mi=min(mi,K[j]);
				if(mi>=L[e]) ret[e]=1;
			}
			
		}
	}
	
	FOR(i,Q) {
		if(ret[i]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	
}

まとめ

最初思いついたのが、基底ベクトルを保ちながら平面走査だった。
ただ、基底ベクトルを合成して同じbitが1か所でしか立たないようにする処理を考慮してなかったので、これだとTLEしてたな。