洛谷题单指南-分治与倍增-P4155 [SCOI2015] 国旗计划

原题链接：https://www.luogu.com.cn/problem/P4155

题意解读：在m个点的环上，有n个区间，且各个区间之间没有包含关系，计算从每个区间开始，最少要多少个区间能覆盖环上所有m个点。

解题思路：

本质上是一个区间覆盖问题！

1、破环成链

由于题目中是一个环，对于环的问题，在区间DP中介绍过，经典处理是破环成链，并且延展两倍长度。

2、区间覆盖

从某一个区间开始，要用最少的区间覆盖长度m的点，可以用经典的区间覆盖贪心算法：

先将区间按左端点排序，对于一个区间i，l[i]~r[i]，下一个区间j，必须满足l[j] < r[i]并且r[j]经可能远。

由于题目说明“每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含”，即各个区间之间没有包含关系，

可以认为区间的左端点越大则右端点也越大，因此对于区间i的下一个区间j，就是满足l[j] <= r[i]的最后一个区间。

如果对于每一个区间，都执行一遍区间覆盖贪心算法，统计区间数，总体复杂度为O(n^2)，会超时！

3、倍增预处理

借助于倍增ST表思想，可以将从每个区间开始跳2^k个区间之后到哪个区间进行初始化，即从某个士兵传递2^k次国旗后到哪个士兵

设go[i][j]表示从第i个士兵开始，传2^j次国旗后到哪个士兵

借助于区间覆盖算法，可以初始化go[i][0]为从i区间跳1次后到的区间，然后通过递推可计算go[i][j] = go[go[i][j - 1]][j - 1]

4、倍增计算

对于从start区间开始，最少经过多少个区间能覆盖m个点，可以借助倍增思想

从可以跳的最多次数x开始递减，找到go[start][x]区间右端点距离起点区间左端点正好少于m个点的x，start更新为go[start][x]，累加x，直到超过m个点，记录从该起点开始的答案。

5、记录答案

由于将士兵（区间）进行了排序，要保留原来的序号，记录序号对应的答案。

最后输出所有答案即可，总体复杂度是O(n * logn)

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

struct node
{
    int id, l, r;
} a[2 * N];

int go[2 * N][20]; //go[i][j]表示从第i个士兵开始，传2^j次国旗后到哪个士兵
int n, m;
int ans[N];

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        a[i].id = i;
        scanf("%d%d", &a[i].l, &a[i].r);
        if(a[i].r < a[i].l) 
        {
            a[i].r += m; //对于右端点比左端点小的情况，要加上m
        }
    } 
    sort(a + 1, a + n + 1, cmp);
    //破环成链，复制两倍长度
    for(int i = 1; i <= n; i++)
    {
        a[i + n].l = a[i].l + m;
        a[i + n].r = a[i].r + m;
    }
    //初始化go
    for(int i = 1, j = i; i <= 2 * n; i++) //这里双指针i，j的使用很关键，不能在下面每次都定义j=i，这样就是O(n*n)了，会超时
    {
        while(j <= 2 * n && a[j].l <= a[i].r) j++;
        go[i][0] = j - 1; //用区间覆盖算法找到i的下一个区间
    }
    for(int j = 1; j < 20; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= 2 * n; i++)
        {
            go[i][j] = go[go[i][j - 1]][j - 1];
        }
    }
    //倍增计算
    for(int start = 1; start <= n; start++)
    {
        int t = start;
        int cnt = 1;
        for(int x = 19; x >= 0; x--)
        {
            int end = go[t][x]; //从t跳2^x次到end
            if(end != 0 && a[end].r - a[start].l + 1 <= m) 
            {
                cnt += 1 << x;
                t = end;
            }
        }
        ans[a[start].id] = cnt + 1; //跳了cnt次覆盖了不超过m个点，还要跳一次才能覆盖第m个点到第1个点之间的空隙
    }
    //输出结果
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);

    return 0;
}