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; }