欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF1175E Minimal Segment Cover

程序员文章站 2022-06-28 21:17:22
题目链接 题意 给出n条线段。m次询问,每次询问给出一个区间$[l,r]$问最少需要多少条线段才能覆盖区间$[l,r]$。 所有坐标$\le 5\times 10^5$。$n,m\le 2\times 10^ 5$ 思路 其实是比较经典的线段覆盖问题。 $f[i][j]$表示从i开始走$2^j$条线 ......

题目链接

题意

给出n条线段。m次询问,每次询问给出一个区间\([l,r]\)问最少需要多少条线段才能覆盖区间\([l,r]\)
所有坐标\(\le 5\times 10^5\)\(n,m\le 2\times 10^ 5\)

思路

其实是比较经典的线段覆盖问题。

\(f[i][j]\)表示从i开始走\(2^j\)条线段最远到达的位置。

然后对于每次询问都走一遍即可。

代码

/*
* @author: wxyww
* @date:   2019-06-06 10:55:48
* @last modified time: 2019-06-06 14:54:02
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 1000000 + 100,logn = 23;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int f[n][logn + 1];
int query(int l,int r) {
    ll ans = 0;
    for(int i = logn - 1;i >= 0;--i) { 
        if(f[l][i] < r) {
            l = f[l][i];
            ans += (1 << i);
        }
    }
    l = f[l][0];ans++;
    if(l < r) return -1;
    return ans;

}
int main() {
    int n = read(),m = read();
    int mx = 0;
    for(int i = 1;i <= n;++i) {
        int l = read() + 1,r = read() + 1;
        f[l][0] = max(f[l][0],r);
        mx = max(mx,r);
    }

    for(int i = 1;i <= mx;++i) f[i][0] = max(f[i][0],max(i,f[i - 1][0]));

    for(int j = 1;j < logn;++j) 
        for(int i = 1;i <= mx;++i) 
            f[i][j] = f[f[i][j - 1]][j - 1];

    while(m--) {
        int l = read() + 1,r = read() + 1;
        printf("%d\n",query(l,r));
    }
    return 0;
}