kmjp's blog

競技プログラミング参加記です

第五回 アルゴリズム実技検定 : N - 旅行会社

これも割とすんなり。
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問連続二分探索解でいいんかな。