いろはちゃんコンテスト Day1 : L - をあ ぷろぶれむ

これは典型かな…。
https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_l

問題

N要素の整数列Aが与えられる。
部分列N*(N+1)/2通りに対し、要素同士のorを取った値を降順に並べたとき、K番目の値はいくつか。

解法

二分探索で「V以上の値はK個以上ある」というようなVを求めよう。

V以上の数の数え上げだが、左端を走査しつつ、条件を満たす最も左の右端を順次求めていけばよい。
SegTreeでやってもよいし、自分はbit毎に最寄りの1が立る位置を前処理で求めておきそれを用いた。

int N;
ll K;
ll A[101010];
int nex[202020][60];

ll num(ll v) {
	ll ret=0;
	int i,j;
	FOR(i,N) {
		int cur=i;
		int mi=N;
		for(j=59;j>=0;j--) {
			if(v&(1LL<<j)) {
				cur=max(cur,nex[i][j]);
			}
			else {
				mi=min(mi,max(nex[i][j],cur));
			}
		}
		ret+=(N-min(mi,cur));
	}
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	
	FOR(i,60) nex[N][i]=N;
	for(i=N-1;i>=0;i--) {
		FOR(j,60) {
			nex[i][j]=nex[i+1][j];
			if(A[i]&(1LL<<j)) nex[i][j]=i;
		}
	}
	
	ll ret=(1LL<<60)-1;
	if(num(ret)>=K) {
		cout<<ret<<endl;
		return;
	}
	
	for(i=59;i>=0;i--) if(num(ret^(1LL<<i))<K) ret-=1LL<<i;
	
	cout<<ret-1<<endl;
	
	
	
}

まとめ

xorの方が難しそう。