题解 CF1175E Minimal Segment Cover

发表于 分类于 阅读次数： Valine： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

我们先考虑一下一道“缩水版”的题目。

已知数轴上有一个区间，左端点记为 LL，右端点记为 RR，以及 nn 条线段 sis_i，请问在 nn 条线段中最少选择多少条，可以把区间完全覆盖（包括 LL 点和 RR 点）。

我们可以定义 fif_i 表示从 ii 这个点，通过一条线段能到达的最右的点。

实现方式：

1
2
3
4
5
rep(i,1,MAXR) f[i]=i; //MAXR是值域
rep(i,1,n) {
    f[s[i].l]=max(f[s[i].l],s[i].r);
}
rep(i,0,MAXR) f[i]=max(f[i],f[i-1]);

然后暴力从 LL 开始跳 ff 即可。

如果遇到了 fi=if_i=i 且 i<Ri<R 的情况，那么无解。

跳到 RR 以后 break 掉循环。

那么可以来看这道题目了。如果说要优化一次询问的过程呢？

可以倍增！设 fi,jf_{i,j} 表示从 ii 这个点通过 2j2^j 个线段能到达的最右的点。

这样一次询问我们就优化成了 O(log⁡n)O(\log n)，可以通过本题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=2e5+5,MAXL=5e5+5;
int n,m,fare[MAXL][22];
int mxr=0;
int main() {
    scanf("%d%d",&n,&m);
    rep(i,1,n) {
        int l,r;
        scanf("%d%d",&l,&r);
        fare[l][0]=max(fare[l][0],r);
        mxr=max(mxr,r);
    }
    rep(i,0,mxr) fare[i][0]=max(fare[i][0],fare[i-1][0]);
    rep(j,1,21) rep(i,0,mxr) {
        fare[i][j]=fare[fare[i][j-1]][j-1];
    }
    rep(i,1,m) {
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=0;bool flg=0;
        per(j,21,0) {
            if(fare[x][j]<y) {
                ans+=(1<<j);
                x=fare[x][j];
            }
        }
        if(fare[x][0]>=y) printf("%d\n",ans+1);
        else puts("-1");
    }
	return 0;
}