Codeforces #1051 : Div2. F. Increasing Xor

なんかこういうのCodeforcesに多い印象あるな。
https://codeforces.com/contest/2143/problem/F

問題

整数列Aが与えられる。
クエリとしてその部分列が指定されるので、以下の問題に答えよ。

• 部分列をBとする。2要素i,j(i＜)を選び、B[j] = B[j] xor B[i]で更新することを任意回数行えるとする。
• Bを狭義単調増加にできるか判定せよ。

解法

後ろの要素は、手前の任意の要素のxorを足しこめる。

部分列の左端に対し、右端をどこまで伸ばせるかをあらかじめ伸ばしておく。
B[0],B[1],....,と並べたとき、新たな基底ベクトルを構成できるタイミングがB[a]、B[b]、B[c]....とする。
B[0]...B[a]まで条件を満たしたとき、B[a]の最小値がvとする。するとB[a+1]～B[b-1]は、B[0]...B[a]の基底ベクトルをbit vectorとみなし、その最小値を足しこんでいったものとする。
そうして、基底ベクトルで表しきれる値の上限を超えないような範囲が、右端の取りえる範囲となる。

int T,N,Q;
int A[202020];

int L[202020];
int R[202020];


vector<int> add[202020];

int left(vector<int> B, int v) {
	FORR(t,B) v=min(v,t^v);
	return v;
}
void addv(vector<int>& B, int v) {
	FORR(t,B) v=min(v,t^v);
	FORR(t,B) t=min(t,t^v);
	B.push_back(v);
	sort(ALL(B));
}
int order(vector<int>& B, int v) {
	int ret=0;
	int i;
	int ov=v;
	for(i=B.size()-1;i>=0;i--) {
		if((v^B[i])<v) {
			ret+=1<<i;
			v^=B[i];
		}
	}
	assert(v==0);
	return ret;
}
int getval(vector<int>& B, int v) {
	int ret=0;
	int i;
	FOR(i,B.size()) {
		if((v&(1<<i))) ret^=B[i];
	}
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		set<int> S;
		FOR(i,N) {
			cin>>A[i];
			add[i].clear();
			
			int cur=A[i];
			vector<int> B;
			for(auto it=S.rbegin();it!=S.rend();it++) {
				addv(B,A[*it]);
				if(left(B,cur)==0) {
					cur=0;
					L[i]=*it+1;
					S.erase(*it);
					break;
				}
			}
			if(cur) L[i]=0;
			S.insert(i);
			/*
			cout<<i<<" ";
			FORR(s,S) cout<<s;
			cout<<" "<<L[i]<<endl;
			*/
			add[L[i]].push_back(i);
		}
		S.clear();
		FOR(i,N) {
			FORR(e,add[i]) S.insert(e);
			
			int pos=i-1;
			int val=-1;
			vector<int> B;
			int ma=-1;
			FORR(c,S) {
				if(ma>=N) break;
				if(B.empty()) {
					pos=c;
					ma=c+1;
					B.push_back(A[c]);
					val=0;
				}
				else {
					int o=order(B,val);
					int add=c-pos-1;
					if(o+add>=1<<B.size()) break;
					o+=add;
					int v=getval(B,o);
					addv(B,A[c]);
					
					o=order(B,v)+1;
					if(o>=1<<B.size()) {
						ma=c-1;
						break;
					}
					val=getval(B,o);
					pos=c;
					ma=pos+(1<<B.size())-o-1;
				}
			}
			R[i]=ma;
			S.erase(i);
		}
		
		while(Q--) {
			cin>>x>>y;
			x--,y--;
			if(y<=R[x]) cout<<"YES"<<"\n";
			else cout<<"NO"<<"\n";
		}
		
	}
}

まとめ

本番で整理しきれなかった。