杂题——国旗计划(困难)

[SCOI2015] 国旗计划

题目描述

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

样例输入 #1

1
2
3
4
5
4 8
2 5
4 7
6 1
7 3

样例输出 #1

1
3 3 4 3

提示

$$
N\leqslant 2×10^5,M<10^9,1\leqslant C_i,D_i\leqslant M
$$

思路

| |

||

​ ||

​ ||

​ | |

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 2e5 + 10, M = 2 * N;
struct Node {
    int id;
    int L;
    int R;
};

int n, m, n2;
Node w[M];
int res[N], fa[M][20];

bool cmp(Node A, Node B) {
    return A.L < B.L ;
}

void init() {
    int nxt = 1;
    for (int i = 1; i <= n2; i++){
        // nxt = i;
        while(nxt <= n2 && w[nxt].L <= w[i].R) {
            nxt++;
        }
        fa[i][0] = nxt - 1;
        // 记录走一次可以走到的最优解位置，这里还运用到了一点贪心思路，按照一般思路，这里nxt在每次遍历的时候都应该进行一个初始化操作nxt = i的，但是我们可以推出不需要进行这一步操作的,为什么呢？我们可以先这样思考，我们的nxt如果出现回溯的情况这代表着什么呢，实际上代表的是我们枚举的这个区间和上一个区间是不是就出现了包含关系比如思路的那张图，只有这种情况才会出现nxt回溯的情况，但是由标红自体可知这是不可能出现的，换句话就是这道题目所有的区间按照左端点从小到大排序好之后右端点是单调递增。
        
    }
    
    // ST递增算法的具体体现，本题最难的地方，这个地方的讲解之后会更新。
    for (int i = 1; (1 << i) <= n; i++) {
        for (int s = 1; s <= n2; s++) {
            fa[s][i] = fa[fa[s][i - 1]][i - 1];
        }
    }
}

void getans(int x){
    int len = w[x].L + m, cur = x, ans = 1;
    for (int i = log2(N); i >= 0; i--){
        int pos = fa[cur][i];
        if (pos && w[pos].R < len) {
            ans += 1 << i;
            cur = pos;
        }
    }
    res[w[x].id] = ans + 1;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        w[i].id = i;
        cin >> w[i].L >> w[i].R;
        if (w[i].L > w[i].R) w[i].R += m;
    }
    
    sort(w + 1, w + n + 1, cmp);
    n2 = n;
    for (int i = 1; i <= n; i++) {
        n2++;
        w[n2] = w[i];
        w[n2].L = w[i].L + m;
        w[n2].R = w[i].R + m;
    } 
    
    init();
    
    for (int i = 1; i <= n; i++) getans(i);
    for (int i = 1; i <= n; i++) cout << res[i] << " ";
    return 0;
}