题目概述

在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，问第 $i$ 个线段必选时至少需要多少线段能够覆盖这个环。

解题报告

和BZOJ5397差不多，唯一要注意的就是在BZOJ5397中不需要在 $s>t$ 时建 $(s+m,t+m+m)$ 这样的线段（因为用不到），但这道题需要。而且题目保证线段没有包含关系，好评，不然还要自己去重。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=400000,Log=19;

int m,n,ST[maxn+5][Log+5],ans[maxn+5];
struct data {int fr,sc,ID;} s[maxn+5];

inline int Maxer(int x,int y) {return s[x].sc>s[y].sc?x:y;}
inline int Find(int L,int R,int x){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        s[mid].fr>x?R=mid-1:L=mid+1;return L-1;
}
inline bool cmp (const data &a,const data &b) {return a.fr<b.fr;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    int N;scanf("%d%d",&N,&m);
    for (int i=1;i<=N;i++){
        int x,y;scanf("%d%d",&x,&y);
        if (x>y) s[++n]=(data){x,y+m,i},s[++n]=(data){x+m,y+m+m,0};
        else s[++n]=(data){x,y,i},s[++n]=(data){x+m,y+m,0};
    }
    sort(s+1,s+1+n,cmp);
    for (int i=n-1;i;i--){
        ST[i][0]=Find(i+1,n,s[i].sc);
        for (int j=1;j<=Log;j++) ST[i][j]=ST[ST[i][j-1]][j-1];
    }
    for (int i=1;i<=n;i++)
        if (s[i].ID){
            int R=i,num=2;
            for (int j=Log;~j;j--) if (ST[R][j]&&s[ST[R][j]].sc<s[i].fr+m) R=ST[R][j],num+=1<<j;
            ans[s[i].ID]=num;
        }
    for (int i=1;i<N;i++) printf("%d ",ans[i]);printf("%d\n",ans[N]);return 0;
}