codeforces1175E Minimal Segment Cover 倍增

题意：给出n条平行于x轴的线段，q次询问，每次询问一个区间最少要几条线段来覆盖，若不能覆盖则输出-1.

思路：先考虑贪心，必定是先找到，所有左端点小于等于$x$的线段的右端点最大在哪里，然后答案加一，将$x$挪到这个最大右端点，继续贪心，直到右端点大于$y$。

　　考虑优化，可以用倍增来加速这个过程，先用初始的线段预处理出所有的$f[i][j]$，代表第i个节点跳跃{2^j}个线段最大能到达多少个右端点，然后倍增搞一下，每次询问的时候，也是二分的跳，每次的时间复杂度都是$log(n)$，总的时间复杂度是$nlog(n)$。

#pragma GCC optimize (2)

#pragma G++ optimize (2)

#pragma comment(linker, "/STACK:102400000,102400000")

#include<bits/stdc++.h>

#include<cstdio>

#include<vector>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define dep(i,b,a) for(int i=b;i>=a;i--)

#define clr(a,b) memset(a,b,sizeof(a))

#define pb push_back

#define pii pair<int,int >

using namespace std;

typedef long long ll;

const int maxn=;

ll rd()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int f[maxn][],maxx,x,y,n,q;

int fac[];

int main(){

    fac[]=;

    rep(i,,){

        fac[i]=*fac[i-];

    }

    while(cin>>n>>q){

        clr(f,);

        rep(i,,n){

            scanf("%d%d",&x,&y);

            f[x][]=max(f[x][],y);

        }

        maxx=;

        rep(i,,maxx){

            f[i][]=max(f[i][],f[i-][]);

            if(f[i][]<=i)f[i][]=;

        }

//        puts("debug");

        rep(i,,){

            rep(j,,maxx){

                if(f[j][i-]!=&&f[f[j][i-]][i-]!=){

                    f[j][i]=f[f[j][i-]][i-];

                }

            }

        }

        while(q--){

            scanf("%d%d",&x,&y);

            int r=x;

            int ans=;

            dep(i,,){

                if(f[r][i]==)continue;

                if(f[r][i]<y){

                    ans+=fac[i];

                    r=f[r][i];

                }

            }

            if(f[r][]>=y){

                printf("%d\n",ans+);

            }else{

                puts("-1");

            }

        }

    }

}

巴特西

codeforces1175E Minimal Segment Cover 倍增

最新文章

热门文章