4444: [Scoi2015]国旗计划

A国正在开展一项伟大的计划——国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这

项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了N名优秀的边防战上作为这

项计划的候选人。

A国幅员辽阔，边境线上设有M个边防站，顺时针编号1至M。每名边防战士常驻两个边防站，并且善于

在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。n名边防战士

都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。

现在，国十安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，

从而顺利地完成国旗计划。不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必

须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利地完成国旗计划。

第1行，包含2个正整数N,M，分别表示边防战士数量和边防站数量。

随后n行，每行包含2个正整数。其中第i行包含的两个正整数Ci、Di分别表示i号边防战士常驻的两个边防站编号，

Ci号边防站沿顺时针方向至Di号边防站力他的奔袭区间。数据保证整个边境线都是可被覆盖的。

输出数据仅1行，需要包含n个正整数。其中，第j个正整数表示j号边防战士必须参加的前提下至少需要

多少名边防战士才能顺利地完成国旗计划

4 8
2 5
4 7
6 1
7 3

3 3 4 3

n≤2×10^5，M< 10^9，1≤Ci，Di≤M

分析

每一个区间都不能被其他区间所包含，也就是如果

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<set>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 400100;
 9 const int INF = 0x7fffffff;
10 
11 struct Peo{
12     int l,r,id;
13     bool operator < (const Peo &a) const
14     {
15         return l < a.l;
16     }
17 }p[MAXN];
18 
19 int f[MAXN][30],ans[MAXN];//f[i][j]表示从i点走2^j步到达的点 
20 int tot,n,m;
21 set< pair<int,int> >s;
22 
23 int read()
24 {
25     int x = 0,f = 1;char ch = getchar();
26     while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch = getchar(); }
27     while (ch>='0'&&ch<='9'){x = x*10+ch-'0';ch = getchar(); }
28     return x*f;
29 }
30 
31 void work(int x)
32 {
33     int d = p[x].id, L = p[x].l+m;
34     for (int i=20; i>=0; --i)
35         if (f[x][i])
36             if (p[f[x][i]].r<L) 
37                 x = f[x][i],ans[d] += (1<<i);
38 }
39 
40 int main()
41 {
42     n = read(),m = read();
43     for (int x,y,i=1; i<=n; ++i)
44     {
45         x = read();y = read();
46         if (y<x) y += m;
47         p[++tot].l = x; p[tot].r = y; p[tot].id = i;
48         p[++tot].l = x+m;p[tot].r = y+m;    
49     }
50     
51     sort(p+1,p+tot+1);
52     s.insert(make_pair(p[tot].l,tot));
53     for (int i=tot-1; i; --i)
54     {
55         f[i][0] = (--s.upper_bound(make_pair(p[i].r,INF)))->second; 
56         s.insert(make_pair(p[i].l,i));
57     }
58     
59     for (int i=1; i<=20; ++i)
60         for (int j=tot; j; --j)
61             f[j][i] = f[f[j][i-1]][i-1];
62     for (int i=1; i<=tot; ++i)
63         if (p[i].id) work(i);
64         
65     for (int i=1; i<=n; ++i)
66          printf("%d ",ans[i]+2);
67     return 0;
68 }