Codeforces 1175E (倍增)

Codeforces 1163E
题意：给定$n$个区间$[l_i, r_i]$，$m$次询问用最小的区间覆盖$[x,y]$

发现对于一个点，所有包含他的区间只有$r$最远区间的有用，因为直接选这个区间一定最优
所以我们可以用并查集或者线段树预处理每个点所有包含他的区间最远的$r$，然后我们就可以一步步的跳然后找到答案。
这里一步步跳，我们联想到倍增优化，那么预处理一下倍增即可。
但是这里还要考虑一下不存在方案的情况。
那么对区间在轴上区间增加，如果一个地方的值等于0说明这中间断开了，处理一下即可。
更好的实现我们考虑一个区间，所有和他相交区间只有$r$最远区间的有用，按照上面的方法处理一下即可。

知识点：
1、需要跳的题面可以考虑倍增优化

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 5, LOGS = 20;

    int n, m, c[MAXN], tax[MAXN], pre[MAXN][LOGS + 2];
    struct data {
        int l, r;
    } qj[200000 + 5];

    bool cmp (data a, data b) {
        if (a.l == b.l) return a.r > b.r;
        return a.l < b.l;
    }

    void clean() {
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) scanf("%d%d", &qj[i].l, &qj[i].r), qj[i].r--;
        sort(qj + 1, qj + 1 + n, cmp);
        int tmp = n; n = 1;
        c[qj[1].l]++, c[qj[1].r + 1]--;
        for (int i = 2; i <= tmp; ++i) if (qj[i].r > qj[n].r) qj[++n] = qj[i], c[qj[n].l]++, c[qj[n].r + 1]--;

        if (!c[0]) tax[0] = 1;
        for (int i = 1; i <= 500000; ++i) {
            c[i] += c[i - 1];
            if (!c[i]) tax[i] = 1;
            tax[i] += tax[i - 1];
        }

        int j = 2;
        for (int i = 1; i <= n; ++i) {
            j = max(j, i + 1);
            while (j <= n && qj[j].l <= qj[i].r + 1) ++j;
            if (i != j - 1) pre[i][0] = j - 1;
        }

        for (int j = 1; j <= LOGS; ++j) {
            for (int i = 1; i <= n; ++i) {
                pre[i][j] = pre[pre[i][j - 1]][j - 1];
            }
        }

        while (m--) {
            int x, y; scanf("%d%d", &x, &y), --y;
            int cnt = tax[y];
            if (x) cnt -= tax[x - 1];
            if (cnt) printf("-1\n");
            else {
                int p = lower_bound(qj + 1, qj + 1 + n, (data){x + 1, (int)1e9}, cmp) - qj - 1;
                if (qj[p].r >= y) {
                    printf("1\n");
                    continue ;
                } else {
                    int ans = 0;
                    for (int i = LOGS; i >= 0; --i) {
                        if (qj[pre[p][i]].r < y && pre[p][i]) {
                            p = pre[p][i];
                            ans += 1 << i;
                        }
                    }
                    printf("%d\n", ans + 2);
                }
            }
        }

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}