传送门

题意是给定N个区间，询问M个区间最少能用多少个给定的线段覆盖，允许重合/超过。

首先很明显的是被某个区间完全覆盖的小区间是没有用的。

然后需要发现，对于每一个左端点，找到包含这个点而且右端点最远的一个区间肯定是最优解。

那么对于给定区间的右端点，按照降序排列。对排好序的每个区间 i ，这些点最远的右端点就是 i 这个区间的右端点。然后对于下一个区间 j ，小于上一个区间 i 左端点的那些点 的最远右端点就是当前区间 j 的右端点。

这样既消除了被完全覆盖的区间，又找到了包含每个点最远的区间。

然后按照上述关系建立图，实际上是一颗树。

对于每个询问[l, r]，通过树上倍增找到大于r最小的父亲。深度相减就是区间个数。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
struct rec{int l, r;};
bool cmp(const rec &x, const rec &y)
{
    return x.r > y.r;
}
rec a[maxn], b[maxn];
int h[maxn], e[maxn], pre[maxn], cnt;
void add(int u, int v)
{
    e[cnt] = v; pre[cnt] = h[u]; h[u] = cnt++;
}
int mt[maxn];
int fa[maxn][20], d[maxn], t;
void bfs(int s)
{
    queue<int> q;
    q.push(s); d[s] = 1;
    while(q.size())
    {
        int x = q.front(); q.pop();
        for(int i = h[x]; ~i; i = pre[i])
        {
            int y = e[i];
            if(d[y]) continue;
            d[y] = d[x] + 1;
            fa[y][0] = x;
            for(int j = 1; j <= t; j++)
                fa[y][j] = fa[fa[y][j - 1]][j - 1];
            q.push(y);
        }
    }
}
int main()
{
    memset(h, -1, sizeof h);
    memset(mt, -1, sizeof mt);
    //memset(fa, -1, sizeof fa);
    int n, m; cin >> n >> m;
    t = (int)(log(500005) / log(2)) + 1;
    for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].l, &a[i].r), ++a[i].l, ++a[i].r;
    sort(a + 1, a + 1 + n, cmp);
    int mx = 5e5 + 233;
    for(int i = 1; i <= n; i++)
    {
        int k = min(mx, a[i].r);
        for(int j = a[i].l; j < k; j++) mt[j] = a[i].r;
        mx = min(mx, a[i].l);
    }
    //for(int i = 1; i <= 4; i++) cout << mt[i] << ' '; puts("");
    for(int i = 1; i <= 500005; i++) if(~mt[i]) add(mt[i], i);
    for(int i = 1; i <= 500005; i++) if(mt[i] == -1) bfs(i);
    for(int i = 1; i <= m; i++)
    {
        int l, r; scanf("%d%d", &l, &r);
        ++l, ++r;
        int x = l;
        for(int j = t; j >= 0; j--)
            if(fa[x][j]) if(fa[x][j] < r) x = fa[x][j];
        x = fa[x][0];
        //cout << x << '?' << endl;
        if(x >= r) cout << d[l] - d[x] << endl;
        else cout << -1 << endl;
    }
}