Codeforces #932 : Div2 E. Distance Learning Courses in MAC

ストーリーがない方が問題がわかりやすいな…。
https://codeforces.com/contest/1935/problem/E

問題

N要素の整数列X[i],Y[i]が与えられる。
以下のクエリに答えよ。

クエリは区間[L,R]で指定される。L≦j≦Rの各jに対し、値X[j]≦C[j]≦Y[j]を定めたとき、C[j]のbitwise-orを最大化せよ。
Cの値はクエリ毎に変えてよい。

解法

• Y[i]の2^kのbitが立っていたら、C[j]でも2^kのbitを立たせることが可能
• Y[i]の2^kのbitが立っていて、X[i]の2^kのbitが立っていなければ、C[j]でも2^k未満のbitをすべて立たせることが可能

累積和で、区間内でkごとに上記の手順を取れるものが1個以上行えるか高速に求められるようにしておく。

あとは、各クエリに対しbitwise-orの値Vを、上のbitから見て行く。

• 区間内に前者が可能がY[i]が1個でもあれば、Vの2^kのbitを立てる。
• 区間内に前者が可能がY[i]が2個以上あり、後者が可能な(X[i],Y[i])の組が1個でもあれば、Vの2^k未満のbitをすべて立てる。

int T,N;
int X[202020],Y[202020];
int Ys[32][202020],Xs[32][202020];

int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>X[i]>>Y[i];
			FOR(j,30) {
				Ys[j][i+1]=Ys[j][i];
				Xs[j][i+1]=Xs[j][i];
				if(Y[i]&(1<<j)) {
					Ys[j][i+1]++;
					if(X[i]<((Y[i]>>j)<<j)) Xs[j][i+1]++;
				}
			}
		}
		cin>>Q;
		while(Q--) {
			int L,R;
			cin>>L>>R;
			L--;
			
			int ret=0;
			for(i=29;i>=0;i--) {
				if(Ys[i][R]-Ys[i][L]) ret|=1<<i;
				if(Ys[i][R]-Ys[i][L]>1&&Xs[i][R]-Xs[i][L]) ret|=(1<<i)-1;
			}
			cout<<ret<<" ";
		}
		cout<<endl;
	}
}

まとめ

コードは余り長くないな。