题目
题目描述
A 国正在开展一项伟大的计划 —— 国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了 $N$ 名优秀的边防战上作为这项计划的候选人。
A 国幅员辽阔，边境线上设有 $M$ 个边防站，顺时针编号 $1$ 至 $M$。每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。$N$ 名边防战士都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。
现在，国十安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，从而顺利地完成国旗计划。不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利地完成国旗计划。
输入输出格式
输入格式：
第一行，包含两个正整数 $N,M$，分别表示边防战士数量和边防站数量。
随后 $N$ 行，每行包含两个正整数。其中第 $i$ 行包含的两个正整数 $C_i$、$D_i$ 分别表示 $i$ 号边防战士常驻的两个边防站编号，$C_i$ 号边防站沿顺时针方向至 $D_i$号边防站力他的奔袭区间。数据保证整个边境线都是可被覆盖的。
输出格式：
输出数据仅 $1$ 行，需要包含 $N$个正整数。其中，第 $j$ 个正整数表示 $j$ 号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划。
输入输出样例
输入样例#1：
4 8
2 5
4 7
6 1
7 3
输出样例#1：
3 3 4 3
说明
$N\leqslant 2×10^5,M<10^9,1\leqslant C_i,D_i\leqslant M$。
题解
首先先破环成链，有一个很明显的贪心，对于某个区间$a$，能选的最优区间$b$一定是$l_b\le r_a$中$r_b$最大的，因为区间互不包含，最优区间肯定是$l_b$最大的
这样确定某个区间$x$后，答案肯定是包含$l_x+m$的最短需要区间，一个一个贪心即可$O(n^2)$做，用倍增优化即可$O(n\log n)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=4e5+5;
struct p{
int l,r,id;
bool operator< (const p &a)
const{
return l<a.l;
}
}a[MAX];
int n,m,cnt;
int id[MAX];
int f[20][MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void Init()
{
for(int i=1;i<20;++i)
for(int j=1;j<=cnt;++j)
f[i][j]=f[i-1][f[i-1][j]];
}
int Solve(int x,int L)
{
int ans=0;
for(int i=19;i>=0;--i)
if(f[i][x]&&a[f[i][x]].r<L) ans+=(1<<i),x=f[i][x];
return ans;
}
int main()
{
n=read(),m=read();
for(int i=1,l,r;i<=n;++i)
{
l=read(),r=read(),a[++cnt].l=l,a[cnt].r=r,a[cnt].id=i;
if(a[cnt].l>a[cnt].r) a[cnt].r+=m,r+=m;
a[++cnt]=(p){l+m,r+m,i};
}
sort(a+1,a+1+cnt);
for(int i=cnt;i>=1;--i)
id[a[i].id]=i;
for(int i=1,L=1;i<=cnt;++i)
{
while(a[L].l<=a[i].r&&L<=cnt) ++L;
if(L-1!=i) f[0][i]=L-1;
}
Init();
for(int i=1;i<=n;++i)
printf("%d ",Solve(id[i],a[id[i]].l+m)+2);
return 0;
}
