题解 | 国旗计划（倍增：区间最值）
国旗计划：原题链接
题意：
输入：第一行给你一个n和m，n代表边防战士的人数，m代表总共有几个站点，接下来有n行，每行给你两个站点C和D，战士行走的区间为[C,D]，区间会重叠，但不会完全覆盖。
输出：输出每个战士，在以他自身的区间为起点的前提下，至少需要多少人可以使战士之间行走的区间形成一个环。
做题思路：
初步入手本题，可以想到如果要判断成环，最好的办法是将环拆分成链，即当右边的点小于左边的点时，说明该点跨过了环，因此将右边的点加上站点总数，即可生成假设在一条链上的两点间的距离。
初始输入代码：
cin >>n>>m;
for (int i=1;i<=n;i++)
{
cin >>w[i].l>>w[i].r;
//破环成链
if (w[i].r<w[i].l)w[i].r+=m;
}
在生成完链后，题目要求也变成了找到覆盖3-10的这个区间，问题是该怎么求解，找到最少的人数去覆盖这个区间，这里可以先试用贪心的思想进行思考，因为战士之间的区间是不会完全覆盖的，所以只要每次是下一个选中区间的起点是当前区间中，最靠近选择区间末的区间，即可完成最少人数成环这一条件。
以此为依据，在原先来链的基础上，再copy（复制）一份每个区间都加上一个环时的情况，用以判断当区间跨过环时，存在2-5的区间，但无法求解的情况，同时，因为题目只规定了战士不会被完全覆盖，但其顺序可能是被打乱的，所以为了满足区间查找的单调性，对数组进行sort排序。
改进后输入代码：
//输入+处理
cin >>n>>m;
for (int i=1;i<=n;i++)
{
//记录id，在输出结果时，是原序输出
w[i].id=i;
cin >>w[i].l>>w[i].r;
//破环成链
if (w[i].r<w[i].l)w[i].r+=m;
}
//起点排序
sort(w+1,w+n+1);
//复制一份
n2=n*2;
for (int i=n+1;i<=n2;i++)
{
w[i]=w[i-n];
w[i].l+=m;
w[i].r+=m;
}
接下来是查找区间，但注意，如果直接查找区间会导致是o(n^2)的时间复杂度，也就是超时，因此需要优化区间查找，为此，来到本次题解的重中之中，倍增(st)。
在使用倍增前，先了解倍增的使用条件：必须要有单调性，很显然，这个条件已经满足。
其次是倍增的原理：同二分一样，二分的作用是不断缩减数组，以此来找到需要的数，而倍增则是不断增大。它的运算原理可以参考二进制定理：2^n=2^(n-1)+2^(n-2)+...+2^0+1。
因此其运行规则为：先走2^n步，倘若大于等于数值则说明步数过多，倘若小于，将将步数加上2^n，加至最后，加起来的总步数会是要求步数-1的值。
st的代码：
//贪心选择区间+st生成静态数据
void st()
{
//自建图：
int next=1;
//链上共n2条
for (int i=1;i<=n2;i++)
{
//找到每个区间离右端点最近的左端点所在的区间
while (next <= n2 && w[next].l<= w[i].r)next++;
//记录区间
go[i][0]=next-1;
}
//倍增：i = 1，2，4，8，16..共 logn 次
for (int i=1;(1 << i)<=n;i++)
{
//枚举每条线段
for (int s=1;s<=n2;s++)
{
//若走2^3步，2^3= 2^2+2^2
//先从 s 到走2^2步到中转站
//再从中转站走2^2到终点
go[s][i]=go[go[s][i-1]][i-1];
}
}
}
构建完图后，即可运用图表进行求解每位士兵的最少人数，即st的调用。
//st的使用
void getRes(int x)
{
//len为终点长度，该长度代表能否成环
//now为初始的节点
//ans记录人数，因为放入了自身的初始节点，所以人数至少为1
int len=w[x].l+m,now=x,ans=1;
//i初始为log2(n),20是为了方便计算
for (int i=20;i>=0;i--)
{
//从大到小开始查找
int to=go[now][i];
//当to存在,长度在len内
if (to && w[to].r<len)
{
ans=ans+(1<<i); //累加跳过的区域
now=to;//从新位置开始
}
}
//记录时使用id记录人数，毕竟sort过了，但输出要使用原序列
//ans+1因为ans是小于len的，还无法成环，
//但因为st性质，他的下一步必定大于len，此时可以成环
res[w[x].id]=ans+1;
}
最后直接输出存入的数值，即可得出答案，这里直接放ac代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
int n, n2, m;
struct Index{
int id,l,r;//编号+区间
//以起始点小的排序
bool operator<(const Index &b) const { return l< b.l;}
};
Index w[maxn*2];//破环成链,因此空间需要开两份
int go[maxn][25];//倍增记录自建图
int res[maxn];//记录结果
//贪心选择区间+st生成静态数据
void st()
{
//自建图：
int next=1;
//在链上选择共n2条
for (int i=1;i<=n2;i++)
{
//每个区间的下一个右端点最大的区间
while (next <= n2 && w[next].l<= w[i].r)next++;
//区间i的下一个区间
go[i][0]=next-1;
}
//倍增：i = 1，2，4，8，16..共 logn 次
for (int i=1;(1 << i)<=n;i++)
{
//枚举每条线段
for (int s=1;s<=n2;s++)
{
//若走 2^3 步，2^3= 2^2+2^2
//先从 s 到走2^2步到中转站
//再从中转站走2^2到终点
go[s][i]=go[go[s][i-1]][i-1];
}
}
}
//st的使用
void getRes(int x)
{
//len为终点长度，该长度代表能否成环
//now为初始的节点
//ans记录人数，因为放入了自身的初始节点，所以人数至少为1
int len=w[x].l+m,now=x,ans=1;
//i初始为log2(n),20是为了方便计算
for (int i=20;i>=0;i--)
{
//从大到小开始查找
int to=go[now][i];
//当to存在,长度在len内
if (to && w[to].r<len)
{
ans=ans+(1<<i); //累加跳过的区域
now=to;//从新位置开始
}
}
//记录时使用id记录人数，毕竟sort过了，但输出要使用原序列
//ans+1因为ans是小于len的，还无法成环，
//但因为st性质，他的下一步必定大于len，此时可以成环
res[w[x].id]=ans+1;
}
int main(){
//输入+初步处理
cin >>n>>m;
for (int i=1;i<=n;i++)
{
w[i].id=i;
cin >>w[i].l>>w[i].r;
//破环成链
if (w[i].r<w[i].l)w[i].r+=m;
}
//起点排序
sort(w+1,w+n+1);
//复制一份
n2=n*2;
for (int i=n+1;i<=n2;i++)
{
w[i]=w[i-n];
w[i].l+=m;
w[i].r+=m;
}
//倍增(st)开始
st();
//循环得出每个节点的最少成环人数
for (int i=1;i<=n;i++)getRes(i);
//输出答案
for (int i=1;i<=n;i++)cout <<res[i]<<" ";
cout <<"\n";
return 0;
}
投递新环境等公司10个岗位 >
金山WPS公司福利 242人发布