#2007. 「SCOI2015」國旗計劃
題目描述
A 國正在開展一項偉大的計劃 —— 國旗計劃。這項計劃的内容是邊防戰士手舉國旗環繞邊境線奔襲一圈。這項計劃需要多名邊防戰士以接力的形式共同完成，為此，國土安全局已經挑選了 N NN 名優秀的邊防戰上作為這項計劃的候選人。
A 國幅員遼闊，邊境線上設有 M MM 個邊防站，順時針編号 1 11 至 M MM。每名邊防戰士常駐兩個邊防站，并且善于在這兩個邊防站之間長途奔襲，我們稱這兩個邊防站之間的路程是這個邊防戰士的奔襲區間。N NN 名邊防戰士都是精心挑選的，身體素質極佳，是以每名邊防戰士的奔襲區間都不會被其他邊防戰士的奔襲區間所包含。
現在，國十安全局局長希望知道，至少需要多少名邊防戰士，才能使得他們的奔襲區間覆寫全部的邊境線，進而順利地完成國旗計劃。不僅如此，安全局局長還希望知道更詳細的資訊：對于每一名邊防戰士，在他必須參加國旗計劃的前提下，至少需要多少名邊防戰士才能覆寫全部邊境線，進而順利地完成國旗計劃。
輸入格式
第一行，包含兩個正整數 N,M N, MN,M，分别表示邊防戰士數量和邊防站數量。
随後 n nn 行，每行包含兩個正整數。其中第 i ii 行包含的兩個正整數 Ci C_iCi、Di D_iDi 分别表示 i ii 号邊防戰士常駐的兩個邊防站編号，Ci C_iCi 号邊防站沿順時針方向至 Di D_iDi 号邊防站力他的奔襲區間。資料保證整個邊境線都是可被覆寫的。
輸出格式
輸出資料僅 1 11 行，需要包含 n nn 個正整數。其中，第 j jj 個正整數表示 j jj 号邊防戰士必須參加的前提下至少需要多少名邊防戰士才能順利地完成國旗計劃。
樣例
樣例輸入
4 8
2 5
4 7
6 1
7 3 樣例輸出
3 3 4 3 資料範圍與提示
N≤2×105,M<109,1≤Ci,Di≤M N \leq 2 \times 10 ^ 5, M < 10 ^ 9, 1 \leq C_i, D_i \leq MN≤2×105,M<109,1≤Ci,Di≤M
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 400010
using namespace std;
int head[maxn],dep[maxn],s[maxn],ans[maxn];
int n,m,num,t;
struct node{int to,pre;}e[maxn*2];
struct Node{
int l,r,id;
bool operator < (const Node &x)const{
return l<x.l;
}
}q[maxn];
void Insert(int from,int to){
e[++num].to=to;
e[num].pre=head[from];
head[from]=num;
}
void dfs(int now,int father,int h){
dep[now]=dep[father]+1;
s[++t]=now;
if(q[now].id!=0){
while(h<t&&q[s[h+1]].r>=q[now].l+m)h++;
ans[q[now].id]=dep[now]-dep[s[h]]+1;
}
for(int i=head[now];i;i=e[i].pre){
int to=e[i].to;
dfs(to,now,h);
}
t--;
}
int main(){
freopen("Cola.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int l,r;
scanf("%d%d",&l,&r);
if(l>r)r+=m;
q[i].l=l;q[i].r=r;q[i].id=i;
q[i+n].l=l+m;q[i+n].r=r+m;
}
int now=1;
sort(q+1,q+2*n+1);
for(int i=1;i<2*n;i++){
while(now<2*n&&q[i].r>=q[now+1].l)now++;
Insert(now,i);
}
dfs(2*n,0,1);
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
} 自上向下