做法：倍增+贪心

题意：必选一个区间后，找出剩余区间能覆盖整个环的最少区间数

思路：

  • 1.先把环转化成链
  • 2.再把这些区间按左端点排序
  • 3.利用倍增来查询

代码

// Problem: [SCOI2015]国旗计划
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/20302
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=2e5+5;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m;
int lg[N<<1],fa[N<<1][20];
int res[N<<1];

struct soldier{
    int id;
    ll l,r;
}s[N<<1];

bool cmp(soldier a,soldier b){
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}

void init(){
    for(int i=1;i<=(n<<1);i++){
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
}

void search(int u){
    ll l=s[u].l+m;
    int p=u,ans=1;
    for(int i=19;~i;i--){
        if(!fa[u][i]) continue; //fa存在
        if(s[fa[u][i]].r<l){
            ans+=(1<<i);
            u=fa[u][i];
        }
    }
    res[s[p].id]=ans+1; //加自身
}

void solve(){
    cin>>n>>m;
    rep(i,1,n){
        s[i].id=i;
        cin>>s[i].l>>s[i].r;
        if(s[i].l>s[i].r) s[i].r+=m;
    }
    sort(s+1,s+n+1,cmp);
    rep(i,1,n){
        s[i+n].id=s[i].id;
        s[i+n].l=s[i].l+m;
        s[i+n].r=s[i].r+m;
    }
    init();

    int p=1;
    for(int i=1;i<=(n<<1);i++){
        while(p<=(n<<1)&&s[p].l<=s[i].r)
            p++;
        fa[i][0]=p-1;
    }

    for(int i=1;i<=lg[n<<1];i++){
        for(int u=1;u<=(n<<1);u++){
            fa[u][i]=fa[fa[u][i-1]][i-1];
        }
    }

    rep(i,1,n){
        search(i);
    }
    rep(i,1,n) cout<<res[i]<<" ";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}