1175 E. Minimal Segment Cover

$Description$
给你 $n$ 个区间 $l_i \ r_i$ ,有 $m$ 个询问 $x_i \ y_i$ ,问要覆盖 $[x_i,y_i]$ 中所有的点至少需要几个区间.(覆盖的点包括实数点,比如3.5)

$Solution$
倍增写法.首先更新每个区间中左端点 $l_i$ 能扩展到的最远 $r_i$ ,然后 $f[l][0]=max(L[0:l])$ ,倍增更新.
查找时如果 $f[l][i]<r$ ,则 $ans+=2^i\quad l=f[l][i]$ ,因为 $[l,i]$ 中一共有 $2^i$ 个点,无解的时候只要判断 $f[l][0]$ 是否大于 $r$ 即可.

$Code$

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
int n,m;
int L[N];
int f[N][20];
int main(){
    //freopen("in.txt","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int l,r;
        sc("%d%d",&l,&r);
        L[l]=max(L[l],r); 
    }
    f[0][0]=L[0];
    for(int i=1;i<N;i++)L[i]=max(L[i-1],L[i]),f[i][0]=L[i];
    for(int j=1;j<20;j++)
    for(int i=0;i<N;i++)
    f[i][j]=f[f[i][j-1]][j-1];
    while(m--){
        int l,r;
        sc("%d%d",&l,&r);
        int ans=0;
        for(int i=19;i>=0;i--)
        if(f[l][i]<r)ans+=1<<i,l=f[l][i];
        ans++;
        if(f[l][0]<r)o(-1);
        else o(ans);
    }
}