Codeforces #882 : Div2 F. The Boss's Identity

こっちの方がEよりupsolveが多いな。
https://codeforces.com/contest/1847/problem/F

問題

無限長の整数列Aが与えられる。
先頭N項まで明に与えられ、以降はA[i]=A[i-N] | A[i-N+i]で算出される。

以下のクエリに答えよ。

• 整数vが与えられるので、A[i]＞vとなる最小のiを求めよ。

解法

各bit毎に、どこからどこの区間でその値が立つかを記録していく。
あとはクエリをvの降順に並べ替え、上記記録を走査しながらvを下回らない最小の添え字を求めよう。

int T;
int N,Q;
int A[402020];
int nex[30][402020];
ll ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	int sq=0;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) {
			cin>>A[i];
			A[i+N]=A[i];
		}
		FOR(j,30) {
			x=2*N;
			for(i=2*N-1;i>=0;i--) {
				nex[j][i]=x;
				if(A[i]&(1<<j)) x=i;
			}
		}
		
		vector<pair<int,ll>> C;
		FOR(i,N) {
			int cur=A[i];
			C.push_back({cur,i});
			vector<int> S;
			FOR(j,30) if((cur&(1<<j))==0&&nex[j][i]<2*N) S.push_back(nex[j][i]);
			sort(ALL(S));
			FORR(ne,S) {
				cur|=A[ne];
				ll tar=i+1LL*(ne-i)*N;
				if(ne>=N+1) tar-=N;
				C.push_back({cur,tar});
			}
		}
		sort(ALL(C));
		
		vector<pair<int,int>> Qs;
		FOR(i,Q) {
			cin>>x;
			Qs.push_back({-(x+1),i});
		}
		sort(ALL(Qs));
		ll re=1LL<<60;
		MINUS(ret);
		FORR2(v,i,Qs) {
			v=-v;
			while(C.size()&&C.back().first>=v) re=min(re,C.back().second+1), C.pop_back();
			if(re<1LL<<60) ret[i]=re;
		}
		
		FOR(i,Q) cout<<ret[i]<<endl;
		
	}
}

まとめ

確かにEより簡単かも。