题目

题目描述

A国正在开展一项伟大的计划——国旗计划
这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈
这项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了$n$名优秀的边防战士作为这项计划的候选人
A国幅员辽阔，边境线上设有$m$个边防站，顺时针编号$1$至$m$
每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这两个边防战士的奔袭区间
$N$名边防战士都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含
现在，国土安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，从而顺利地完成国旗计划
不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利完成国旗计划

输入格式

输入数据第$1$行，包含$2$个正整数$n$、$m$，分别表示边防战士数量和边防站数量。
随后$n$行，每行包含$2$个正整数
其中，第i行包含的两个正整数$C_i$、$D_i$分别表示i号边防战士常驻的两个边防站编号，$C_i$号边防站沿顺时针方向至$D_i$号边防站为他的奔袭区间
数据保证整个边境线都是可被覆盖的

输出格式

输出数据仅$1$行，需要包含$n$个正整数
其中，第$i$个正整数表示$i$号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划

样例

样例输入

样例输出

3 3 4 3

数据范围与提示

样例说明

若$1$号边防战士必须参加，$1$、$2$、$4$号边防战士可覆盖整个边境线，因此至少需要$3$名边防战士完成国旗计划
同理，若$2$号边防战士或$4$号边防战士必须参加，也需要$3$名边防战士完成国旗计划
若3号边防战士必须参加，则需要$1$、$2$、$3$、$4$号边防战士才能完成国旗计划，因此至少需要$4$名边防战士

数据范围

对于$40\%$的数据，$n\leqslant 2000,m\leqslant 5000$
另有$30\%$的数据，保证所有答案不超过$100$
对于$100\%$的数据，$n\leqslant 2×10^5,m\leqslant 109,1\leqslant C_i,D_i\leqslant m$

题解

因为区间互相不包含，所以可以把区间按照左端点排序，这样右端点一定也是单调的
然后将环拆成一条链，也就是将所以区间在复制一遍
贪心求出每个区间可以走到的下个区间的最远右端点
用$f[x][i]$表示从第$x$个区间出发，走$2^i$个区间到达的区间
用倍增思想，只要右端点$\geqslant$出发的左端点$+m$就可以了
注意要预先保存第$\textbf{i}$个区间的原始下标
附上代码：

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct ppap1
{
    int l,r,h;
}a[500010];
struct ppap2
{
    int to,nxt;
}t[1000010];
int n,m,len,tot,head[500010],ans[500010],f[500010][25];
int cmp(const ppap1 &a,const ppap1 &b)
{
    return a.l<b.l||(a.l==b.l&&a.r<b.r);
}
void add(int u,int v)
{
    t[++tot].nxt=head[u],head[u]=tot,t[tot].to=v;
}
int js(int x)
{
    int ans=0,temp=a[x].l+m;
    for(int i=20;i>=0;i--) if(f[x][i]&&a[f[x][i]].r<temp) x=f[x][i],ans+=(1<<i);
    return ans+2;
}
int main()
{
    scanf("%d%d",&n,&m),len=n;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r),a[i].h=i;
        if(a[i].l>a[i].r) a[i].r+=m;
        else a[++len]=(ppap1){a[i].l+m,a[i].r+m,i};
    }
    sort(a+1,a+len+1,cmp),a[len+1].r=0x7fffffff;
    for(int i=1,z=1;i<=len;i++){
        while(z<=len&&a[z+1].l<=a[i].r) z++;
        f[i][0]=z;
    }
    for(int j=1;j<=20;j++)  for(int i=1;i<=len;i++) f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=len;i++) if(a[i].l<=m) ans[a[i].h]=js(i);
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}