codeforces 1175E 倍增

题意：给你n个区间，m次询问覆盖[X,Y]至少要多少个区间

题解：将p[x][j]定义为以x为开头的倍增1<<j个区间的右端点，剩下的直接求多少j就可以了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10, INF = 0x3f3f3f3f;
#define pi acos(-1.0)
int p[maxn][20];
int main() {
    int n,m,mx;
    scanf("%d%d",&n,&m);
    memset(p,-1,sizeof(p));
    for(int i=0;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        p[x][0]=max(p[x][0],y);
    }
    /* for(int i=0;i<5e5;i++){
        p[i][0]=max(p[i-1][0],p[i][0]);
    }*/
     for (int i = 1; i <= 5e5; i++) {
        if(p[i - 1][0] >= i && p[i - 1][0] > p[i][0])
            p[i][0] = p[i - 1][0];
    }
    for(mx=1;(1<<mx)<=5e5;mx++){
        for(int i=0;i<=5e5;i++){
            if(p[i][mx-1]==-1)p[i][mx]=-1;
            else p[i][mx]=p[p[i][mx-1]][mx-1];
        }
    }
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=0;
        if(p[x][mx-1]<y){
            printf("-1\n");
            continue;
        }
        for(int j=mx-1;j>=0;j--){
            if(p[x][j]<y&&p[x][j]>x){
                ans+=(1<<j);
                x=p[x][j];
            }
        }
        printf("%d\n",ans+1);
    }
    
}