こっちの方が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より簡単かも。