题目描述

A国正在开展一项伟大的计划——国旗计划。
这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。
这项计划需要多名边防战士以接力的形式共同完成，为此，国土安全局已经挑选了 N名优秀的边防战士作为这项计划的候选人。

A国幅员辽阔，边境线上设有 M个边防站，顺时针编号 1至 M。

每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。

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

现在，国土安全局局长希望知道，至少需要多少名边防战士，才能使得他们的奔袭区间覆盖全部的边境线，从而顺利地完成国旗计划。

不仅如此，安全局局长还希望知道更详细的信息：对于每一名边防战士，在他必须参加国旗计划的前提下，至少需要多少名边防战士才能覆盖全部边境线，从而顺利地完成国旗计划。

数据保证整个边境线都是可被覆盖的。

输出格式
输出数据仅 1行，需要包含 N个正整数。

其中，第 j个正整数表示 j号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划。

输入样例

4 8
2 5
4 7
6 1
7 3

输出样例

3 3 4 3

贪心+ST表->倍增

参考左神code

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=4e5+10;
struct Node
{
    int index,left,right;
    bool operator<(const Node &A) const
    {
        return left < A.left;
    }
} tr[N*2];
int stable[N*2][25];
int n, m;
int power;
int ans[N*2];

int st(int start)
{
    int aim = tr[start].left + m;
    int cur = start;
    int res = 0;

    // 预处理阶段，尽可能跳到最远的不超过aim的位置
    for(int p = power; p >= 0; p--) {
        int next = stable[cur][p];
        if(next != 0 && tr[next].right < aim) {
            res += 1 << p;
            cur = next;
        }
    }


    return res+2;
}

signed main()
{
    cin >> n >> m;
    power = log2(n*2);

    // 读取输入并处理环形线段
    for(int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b; // 修正：读取两个值
        tr[i].index = i;
        tr[i].left = a;
        tr[i].right = (b >= a) ? b : b + m; // 处理环形线段
    }

    // 复制线段到下一个周期
    for(int i = 1; i <= n; i++) {
        tr[i+n].index = tr[i].index;
        tr[i+n].left = tr[i].left + m;
        tr[i+n].right = tr[i].right + m;
    }

    sort(tr+1, tr+1+n+n);
    int e = n << 1;

    // 初始化ST表的步数
    for(int i = 1, j = 1; i <= e; i++) {
        while(j <= e && tr[j].left <= tr[i].right) {
            j++;
        }
        stable[i][0] = (j-1 <= e) ? j-1 : 0;
    }

    // 构建ST表
    for(int p = 1; p <= power; p++) {
        for(int i = 1; i <= e; i++) {
            int k = stable[i][p-1];
            stable[i][p] = (k != 0) ? stable[k][p-1] : 0;
        }
    }

    // 计算每个线段的答案
    for(int i = 1; i <= n; i++) {
        ans[tr[i].index] = st(i);
    }

    // 输出结果
    for(int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;

    return 0;
}