『倍增』Minimal Segment Cover

题解

对于区间覆盖类的问题，我们可以想到用培增来解决。

首先，我们需要预处理第一步的操作，即一个店所能够跳到的最远的点。

然后就是倍增，有$f[i][j]=f[f[i][j?1]][j?1].$

然后再是询问，也是一样，不断的条，知道跳到r为止；我们可以一直限制小于$r$，最后加上一个$1$即可。

代码如下：

#include <bits/stdc++.h>using namespace std;
const int N = 800000;int n, m;
int f[N][30];int main(void)
{
    int len = 5e5;scanf("%d %d", &n, &m);for (int i=1;i<=n;++i){
    int l, r;scanf("%d %d", &l, &r);f[l][0] = max(f[l][0],r);}for (int i=1;i<=len;++i)f[i][0] = max(f[i-1][0],f[i][0]);for (int j=1;j<=20;++j)for (int i=0;i<=len;++i)f[i][j] = f[f[i][j-1]][j-1];while (m --){
    int l, r, ans = 0;scanf("%d %d", &l, &r);for (int i=20;i>=0;--i)if (f[l][i] < r) {
    ans += (1<<i);l = f[l][i];}if (ans >= n) puts("-1");else printf("%d\n", ans+1);}return 0;
}