Codeforces #275 Div1 B. Interesting Array

幸い本番すんなり解けた。
http://codeforces.com/contest/482/problem/B

問題

N要素の整数列A[i]がある。
A[i]に対しM個の制限がある。
各制限はL[i]、R[i]、Q[i]からなり、A[L[i]] & A[L[i]+1] & ... & A[R[i]] == Q[i]であることを示す。

全ての制限を満たすA[i]は構築可能か。
可能ならA[i]を答えよ。

解法

まず各制限に関し、A[L[i]] & A[L[i]+1] & ... & A[R[i]] == Q[i]だというならA[L[i]]～A[R[i]]にQ[i]をビット論理和で足しこむ。
そうして生成したA[i]に際し、再度全制限を満たすか判定する。

Aの区間に対するビット論理和の取り方や、論理積の取り方は以下のいずれかが可能。

• SegTreeを使う。O(M*logN)で処理可能
• bit単位の各桁毎にimos法を使いbitのset/clearを設定したり数を判定したりする。O(M*logQ)で処理可能

今回の数値の上限ならどちらでも間に合う。自分は本番に後者を使った。

int N,M;
ll L[100500],R[100500],Q[100500];

int NN[31][100500];
int S[31][100500];
int num[100500];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>L[i]>>R[i]>>Q[i];
		FOR(j,30) if(Q[i]&(1<<j)) NN[j][L[i]-1]++,NN[j][R[i]]--;
	}
	FOR(j,30) {
		x=0;
		FOR(i,N) {
			x+=NN[j][i];
			S[j][i+1]=S[j][i]+(x>0);
			if(x>0) num[i] |= 1<<j;
		}
	}
	FOR(i,M) {
		int ng=0;
		FOR(j,30) {
			if(Q[i]&(1<<j)) {
				if(S[j][R[i]]-S[j][L[i]-1]!=R[i]-L[i]+1) ng|=1<<j;
			}
			else {
				if(S[j][R[i]]-S[j][L[i]-1]==R[i]-L[i]+1) ng|=1<<j;
			}
		}
		if(ng) return _P("NO\n");
	}
	_P("YES\n");
	FOR(i,N) _P("%d ",num[i]);
	_P("\n");
}

まとめ

最初imos法の方がO(M)で速いと思ったけど、桁数分行うので結局SegTreeと大差なかった。