题意

题目链接。

给定一个长度为 $n$ 的环，有 $k$ 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。

解析

先考虑如果是链的话就是一个朴素的贪心：每次在所有左端点不大于当前位置的点中选取一个右端点最大的跳过去。对于环，容易想到将其断开，在其后面复制一份即可。

问题转化为了一个长度为 $2n$ 的链，求最少数量的区域使其能够覆盖长度至少为 $n$ 的一个区间。

朴素的想法是枚举左端点，一直往右跳直至区间长度 $\ge n$。又发现对于任意一个点，其决策是一定的，即我们可以预处理出每一个点会跳到哪个位置，这样的话朴素的往右跳操作就可以用倍增优化，时间复杂度为 $O(n\log n)$。

代码

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e6+5;
int n,k,f[N][30],ans=1e9;
pair<int,int> a[N];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++){
        scanf("%d%d",&a[i].fi,&a[i].se);
        if(a[i].fi>a[i].se) a[i].se+=n;
    }
    sort(a+1,a+1+k);
    int now=1,r=0;
    for(int i=1;i<=2*n;i++){
        while(now<=k&&a[now].fi<=i){
            r=max(r,a[now].se+1);
            now++;
        }
        f[i][0]=r;
    }//预处理跳一次跳到哪
    for(int j=1;j<=20;j++){
        for(int i=1;i<=2*n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }//倍增预处理
    for(int i=1;i<=2*n;i++){
        int x=i,ret=0;
        for(int j=20;j>=0;j--){
            if(f[x][j]-i<n){
                x=f[x][j];
                ret+=1<<j;
            }
        }
        x=f[x][0];ret++;
        if(x-i>=n) ans=min(ans,ret);
    }//枚举左端点再跑倍增即可
    if(ans==1e9) printf("impossible\n");
    else printf("%d\n",ans);
    return 0;
}