思路

这是一道简单的 DP 题，DP 题的核心就是状态转移。

先来说一说 \(dp\) 数组的含义。

\(dp_{i,j}\) 表示从 \(i\) 这个点用 \(2 ^ j\) 条线段能走到的最远的点。

我们再来考虑一下边界情况。

因为我们只用 \(2 ^ 0\) 条线段，那么：\(dp_{i,0} = \max(dp_{i,0},r)\)

接着，我们递推一遍，从前往后更新一遍最大值。

即：\(dp_{i,0} = \max(dp_{i,0},dp_{i - 1,0})\)

然后我们对 \(dp\) 数组进行递增。

即：\(dp_{j,i} = dp_{dp_{j,i - 1},i - 1}\)

注：以上递推和递增的操作都需要从 \(1\) 到 \(N\)，原因是：我们操作都是预处理，最后直接求答案的。

最后，我们直接用一个循环来求出答案。

如果 \(dp_{x,i} < y\)，那么我们的结果直接加上 \(2 ^ i\)，将 \(x\) 更新为 \(dp_{x,i}\)。

结果要加上 \(2 ^ i\) 的原因是：我们从 \(dp\) 数组的含义出发，我们需要的线段数量便是 \(2 ^ i\)

将 \(x\) 更新成 \(dp_{x,i}\) 的原因是：我们把点 \(x\) 之前的所有点都走过了，所以我们直接更新即可

我们最后算出来的结果是终点的上一个点，所以我们需要判断一下最后一个是否有解就行了，如果有解输出结果 + 1，否则输出 -1

Code

#include <bits/stdc++.h>  
  
using namespace std;  
  
const int N = 5e5 + 10;  
int n,m;  
int dp[N + 100000/*要开大一点，不然越界*/][25];  
  
int main(){  
    cin >> n >> m;  
    for (int i = 1;i <= n;i++){  
        int a,b;  
        cin >> a >> b;  
        dp[a][0] = max(dp[a][0],b);  
    }  
    for (int i = 1;i <= N;i++) dp[i][0] = max(dp[i][0],dp[i - 1][0]);  
    for (int i = 1;i <= 19;i++){  
        for (int j = 0;j <= N;j++){  
            dp[j][i] = dp[dp[j][i - 1]][i - 1];  
        }  
    }  
    while (m--){  
        int x,y;  
        int res = 0;  
        cin >> x >> y;  
        for (int i = 19;i >= 0;i--){  
            if (dp[x][i] < y){  
                res += (1 << i);  
                x = dp[x][i];  
            }  
        }  
        if (dp[x][0] >= y) cout << res + 1 << endl;  
        else puts("-1");  
    }  
    return 0;  
}