题意:给出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=500010; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int f[maxn][22],maxx,x,y,n,q; int fac[22]; int main(){ fac[0]=1; rep(i,1,20){ fac[i]=2*fac[i-1]; } while(cin>>n>>q){ clr(f,0); rep(i,1,n){ scanf("%d%d",&x,&y); f[x][0]=max(f[x][0],y); } maxx=500000; rep(i,1,maxx){ f[i][0]=max(f[i][0],f[i-1][0]); if(f[i][0]<=i)f[i][0]=0; } // puts("debug"); rep(i,1,20){ rep(j,0,maxx){ if(f[j][i-1]!=0&&f[f[j][i-1]][i-1]!=0){ f[j][i]=f[f[j][i-1]][i-1]; } } } while(q--){ scanf("%d%d",&x,&y); int r=x; int ans=0; dep(i,20,0){ if(f[r][i]==0)continue; if(f[r][i]<y){ ans+=fac[i]; r=f[r][i]; } } if(f[r][0]>=y){ printf("%d\n",ans+1); }else{ puts("-1"); } } } }