#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 21;
int n, m, Q;
struct section{
	int l,r;
}sec[N];
bool cmp_sec(section x,section y){return x.l < y.l;}
int f[N][M];
int solve(int l,int r){
	int x = l, ans = 0;
	for(int j = 20; j >= 0; j -= 1)
		if(f[x][j] < r){
			x = f[x][j];
			ans += (1 << j);
		}
	return ans + 1;
}
int main(){
	scanf("%d%d%d",&n,&m,&Q);
	for(int i = 1; i <= m; i += 1)
		scanf("%d%d",&sec[i].l,&sec[i].r);
	sort(sec + 1, sec + 1 + m, cmp_sec);
	for(int i = 1, j = 1, r = 0; i <= n; i += 1){
		while(sec[j].l == i && j <= m){
			r = max(r, sec[j].r);
			j += 1;
		}
		f[i][0] = r;
	}
	for(int j = 1; j < M; j += 1)
		for(int i = 1; i <= n; i += 1)
			f[i][j] = f[f[i][j - 1]][j - 1];
	for(int i = 1; i <= Q; i += 1){
		int l, r;
		scanf("%d%d",&l,&r);
		printf("%d\n",solve(l, r));
	}
	return 0;
}

0020

Solution

题意简化：给定若干条线段，多次询问完整覆盖区间 $[l_i,r_i]$ 至少需要多少条线段。

$10pts$

直接暴力

$60pts$

考虑只有单次询问的情形：这是不是就是一道经典的区间覆盖的贪心问题？

对于每一个询问都按照经典贪心的做法来做，最坏时间复杂度为 $O(NQ)$。

$100pts$

我们来回顾一下经典贪心做了一件什么事：

• 查询左端点小于某一特定值的所有线段的右端点的最大值是多少。

那么，其实我们只是把这件事做了 $ans$ 遍，对吧？

众所周知，倍增算法对于优化 “一直在做同一种事” 的算法的效果是很强的，所以把 $60pts$ 的做法套个倍增就结束了。最坏时间复杂度不超过 $O(QlogN)$。