洛谷P4155 [SCOI2015] 国旗计划题解

题目链接：P4155 [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 \le N \le 2\times 10^5,~1 \le M < 10^9,~1 \le C_i,D_i \le M$ 。

考虑断环为链，如果 $l > r$ 就让 $r \gets r + m$ 。另外再拷贝一份 $l+m,r+m$ 。

这样就把我们对于每个战士 $i$ 要覆盖 $[1,m]$ 的要求，改成了覆盖 $[l_i,l_i + m]$ 。

对于固定的右端点 $R$ ，因为线段没有相互包含的关系，所以当 $l$ 相等时 $r$ 一定单调

因此对于每个战士，我们可以预处理出它需要继续覆盖时，选的下一个战士（线段）是谁

可以发现这个东西是有传递性的。考虑倍增。

设 $f(i,j)$ 为第 $i$ 个战士选的第 $2^j$ 个后继者是哪个，则

$f(i,j) = f(f(i,j-1),\,j-1)$

这样我们就能在 $\mathcal{O}(\log n)$ 的复杂度内快速得到答案了。

对了，我们之前拷贝了 $l+m,r+m$ ，而 $(l,r)$ 和 $(l+m,r+m)$ 是不可能同时选中的，~~所以大可放心~~。

总时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int ans[N], f[N * 2][21];
struct node { int l, r, id; } a[N * 2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].l >> a[i].r; a[i].id = i;
        if(a[i].l > a[i].r) a[i].r += m;
    }
    sort(a + 1, a + 1 + n, [](node a, node b) { return a.l < b.l; });
    for(int i = 1; i <= n; i++) a[i + n] = {a[i].l + m, a[i].r + m, -1};
    for(int i = 1, j = 1; i <= 2 * n; i++)
    {
        while(j <= 2 * n && a[j].l <= a[i].r) ++j;
        f[i][0] = j - 1;
    }
    for(int j = 1; j <= 20; j++)
        for(int i = 1; i <= 2 * n; i++) f[i][j] = f[f[i][j - 1]][j - 1];
    for(int i = 1; i <= n; i++)
    {
        int tmp = a[i].l + m, sum = 0, p = i;
        for(int j = 20; ~j; j--)
            if(f[p][j] && tmp > a[f[p][j]].r) { sum += (1 << j), p = f[p][j]; }
        ans[a[i].id] = sum + 2;
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
    return 0;
}