これも割とすんなり。
https://atcoder.jp/contests/past202012-open/tasks/past202012_n
問題
N個の街があり、i番と(i+1)番の街の間は、年齢がL[i]才以上R[i]才以下の人が通行可能である。
以下のクエリに答えよ。
- A才の人がB番の街にいるとき、移動可能な町は何通りか。
解法
区間最大値を取るSegTreeと区間最小値をとるSegTreeを持ち、町番号を増やす方向と減らす方向でどこまで移動可能か、それぞれ二分探索すればよい。
int N,Q; int L[202020],R[202020]; template<class V,int NV> class SegTree_1_ma { public: vector<V> val; static V const def=0; V comp(V l,V r){ return max(l,r);}; SegTree_1_ma(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=comp(v,val[entry]); //上書きかチェック while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; template<class V,int NV> class SegTree_1_mi { public: vector<V> val; static V const def=1<<30; V comp(V l,V r){ return min(l,r);}; SegTree_1_mi(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=comp(v,val[entry]); //上書きかチェック while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1_ma<int,1<<18> sma; SegTree_1_mi<int,1<<18> smi; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N-1) { cin>>L[i]>>R[i]; sma.update(i,L[i]); smi.update(i,R[i]); } while(Q--) { int A,B; cin>>A>>B; B--; int CL=B,CR=B; for(x=20;x>=0;x--) { if(CL-(1<<x)>=0) { int tar=CL-(1<<x); if(sma.getval(tar,B)<=A&&smi.getval(tar,B)>=A) CL=tar; } if(CR+(1<<x)<N) { int tar=CR+(1<<x); if(sma.getval(B,tar)<=A&&smi.getval(B,tar)>=A) CR=tar; } } cout<<(CR-CL+1)<<endl; } }
まとめ
2問連続二分探索解でいいんかな。