CF1175E Minimal Segment Cover（倍增）

类似的贪心思路，肯定找是通过这个点能到的最远的点，这样是最优的。

但是询问次数很多，因此考虑用倍增思想，直接求出每个点通过2^i个边能到的最远点。

这是因为最后的答案一定是最小通过x条边，并且这个x一定能被二进制表示出来

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int f[N][30];
int a[N];
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int i;
    int sign=0;
    for(i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        a[l]=max(a[l],r);
        sign=max(sign,r);
    }
    for(i=1;i<=sign;i++){
        a[i]=max(a[i-1],a[i]);
    }
    for(i=0;i<=sign;i++)
        f[i][0]=a[i];
    for(i=1;i<=25;i++){
        for(int j=0;j<=sign;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    while(m--){
        int l,r;
        int ans=0;
        cin>>l>>r;
        int tmp=l;
        for(i=20;i>=0;i--){
            if(f[tmp][i]<r){
                ans+=(1<<i);
                tmp=f[tmp][i];
            }
        }
        if(a[tmp]>=r){
            cout<<ans+1<<endl;
        }
        else{
            cout<<-1<<endl;
        }
    }
}