[SCOI2015] 国旗计划

题目链接

洛谷

LOJ

题目分析

题意转化为：当必须使用某一条线段时，求覆盖区间至少需要用到的线段数量。

首先题目里出现了环，由于不好处理我们将其拆开成链。

这种区间覆盖问题我们可以使用贪心，根据左端点排序后由于线段不互相包含所以右端单调递增。对于某一条线段，选择最左端在该线段覆盖范围内且最靠右的线段可以使覆盖最优。

而如果暴力去做，由于线段数量能达到 $ 200000 $，每一条线段都要一条条判断下去会超时。这种情况下可以使用倍增进行优化。

定义 $ jump[i][j] $ 为第 $ i $ 条线段后跳过 $ 2^j $ 条线段后到达的线段，有：

\[ jump[i][j] = jump[jump[i][j-1]][j-1] \]

其中 $ jump[i][j-1] $ 是跳了一半的位置，在此基础上再跳那么长就是跳 $ 2^j $ 之后的了。

caution

$ 2^j $ 是中间线段的数量，统计的时候还要加上起跳的线段和到达的线段。

代码实现

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int id;
    int l, r;
};

Node w[400010];
int jump[400010][20];
int ans[200010];
int n, m;

bool cmp(const Node& a, const Node& b)
{
    return a.l < b.l;
}

void pre()
{
    int nxt = 1;
    for (int i = 1; i <= n * 2; i++) {
        //由于已经按照左端点排序并且保证区间不重合，此处不需要将 nxt 重设为 1
        while (nxt <= n * 2 && w[nxt].l <= w[i].r) {
            nxt++;
        }
        jump[i][0] = nxt - 1;
    }
    for (int i = 1; (1 << i) <= n; i++) {
        for (int s = n * 2; s >= 1; s--) {
            // s 循环的正反无所谓，因为使用的是跳了一半的数据，与此层 s 无关
            jump[s][i] = jump[jump[s][i - 1]][i - 1];
        }
    }
}

int query(int x)
{
    int end = w[x].l + m;// 这一圈的结束，下一圈的开始
    int cur = x;
    int ans = 0;

    for (int i = log2(n); i >= 0; i--) {// 2^i 代表一次跳几个边防站
        int pos = jump[cur][i];
        if (w[pos].r < end) {//判断是否完成覆盖
            if (pos) {
                ans += 1 << i;
                cur = pos;
            }
        } else
            break;
        if (pos && w[pos].r < end) {
            ans += 1 << i;
            cur = pos;
        }
    }
    // ans 倍增过程中跳过的线段，要想圆满覆盖还要加上自己本身和最后一根线段
    return ans + 2;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i].l >> w[i].r;
        w[i].id = i;
        if (w[i].r < w[i].l) w[i].r += m;
    }
    sort(w + 1, w + n + 1, cmp); //按照左端点排序以便贪心
    for (int i = 1; i <= n; i++) {
        w[n + i].id = w[i].id;
        w[n + i].l = w[i].l + m;
        w[n + i].r = w[i].r + m;
    }
    pre();
    for (int i = 1; i <= n; i++) {
        ans[w[i].id] = query(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}