题意:给你n条线段[l,r]以及m组询问,每组询问给出一组[l,r],问至少需要取多少个线段可以覆盖[l,r]区间中所有的点。
如果贪心地做的话,可以求出“从每个左端点l出发选一条线段可以到达的最右端点”,然后一直往右跳直到跳到r为止,但最坏情况下需要跳O(n)次显然是会T的,那咋办呢?
我们拓展一下,利用倍增的方法,可以预处理出“从每个左端点l出发选2^k条线段可以到达的最右端点”,设为$dp[l][k]$,则有$dp[l][k]=dp[dp[l][k-1]][k-1]$,对于每组询问,让k从大到小依次尝试,如果从l跳2^k步跳不到到r,那么答案就加上2^k。(非常类似于树上倍增求LCA的过程)
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=5e5+10,inf=0x3f3f3f3f; 5 int dp[N][20],n,m; 6 int main() { 7 scanf("%d%d",&n,&m); 8 while(n--) { 9 int l,r; 10 scanf("%d%d",&l,&r); 11 dp[l][0]=max(dp[l][0],r); 12 } 13 for(int i=1; i<N; ++i)dp[i][0]=max(dp[i][0],dp[i-1][0]); 14 for(int k=1; k<20; ++k) 15 for(int i=0; i<N; ++i) 16 dp[i][k]=dp[dp[i][k-1]][k-1]; 17 while(m--) { 18 int l,r; 19 scanf("%d%d",&l,&r); 20 int ans=0; 21 for(int k=19; k>=0; --k) 22 if(dp[l][k]<r)ans^=(1<<k),l=dp[l][k]; 23 printf("%d\n",dp[l][0]<r?-1:ans+1); 24 } 25 return 0; 26 }