Codeforces ECR #066 : E. Minimal Segment Cover

まぁこれは知ってればすぐかな…。
https://codeforces.com/contest/1175/problem/E

問題

1次元座標において、N個の区間が与えられる。

ここで、Q個のクエリが与えられる。
各クエリは区間で示される。元のN個のうち、最小で何個の区間があればクエリの区間を覆えるか答えよ。

解法

ダブリングを用いる。
まず、前処理として各位置に対し、その位置を含む区間のうち最も右端の座標が大きいものを求めよう。
区間1個で、指定された点を左端とする区間に対し最長どこまで覆えるかがわかる。
あとはこれをダブリングし、各座標から2^n個の区間でどこまで覆えるかを求めよう。

各クエリに対しては、ダブリングの結果を活用すれば、入力の左端から初めて右端まで覆う区間数をO(logN)で求められる。

int N,M;

int R[505050][21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>y;
		R[x][0]=max(R[x][0],y);
	}
	for(i=0;i<=500000;i++) {
		R[i][0]=max({i,R[i-1][0],R[i][0]});
	}
	FOR(x,20) {
		for(i=0;i<=500000;i++) R[i][x+1]=R[R[i][x]][x];
	}
	
	while(M--) {
		cin>>x>>y;
		int num=0;
		for(i=19;i>=0;i--) {
			if(R[x][i]<y) {
				x=R[x][i];
				num+=1<<i;
			}
		}
		
		if(R[x][0]>=y) {
			cout<<(num+1)<<endl;
		}
		else {
			cout<<-1<<endl;
		}
	}
	
	
}

まとめ

典型だしEducationalな問題。