题意

给你一个长度为 \(len\) 的环，以及 \(n\) 个区间，要你选择尽量少的区间，使得它们完全覆盖整个环。问最少要多少个区间。

\(len,n\leq 10^6\) .

分析

• 考虑普通的区间覆盖的贪心做法，这里只需要倍增一下。

• 如果区间 \(r< l\) 把 \(r\) 设置成 \(r+len\) 。

• 每个解都一定存在一个区间满足其标号最小，且可以通过后面的区间跳回自己的右边，只需要以这类区间开头即可。

• 总时间复杂度为 \(O(nlogn)\) .

处理区间覆盖的技巧：记录后缀最小值 \(mn\)，如果\(mn\leq l+1\) 就让指针++.这样就可以找到最靠后的满足要求的位置。

倍增的时候注意：如果不存在这么长的转移是不能够转移的，否则可能答案(步数)会算大。

代码

#include
    
     using namespace std;#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)#define rep(i,a,b) for(int i=a;i<=b;++i)#define pb push_backtypedef long long LL;inline int gi(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}    return x*f;}template
     
      inline bool Max(T &a,T b){return a
      
       
        inline bool Min(T &a,T b){return b
        
         =len) Min(ans,s);    }    if(ans==inf) puts("impossible");    else printf("%d\n",ans);    return 0;}