（倍增）洛谷 P1613 跑路/P4155 国旗计划

倍增就是把一步一步跳，变成每次跳 $2^k$，把 $O(n)$ 变 $O(\log n)$，提高效率。经典应用是求 lca，以下是核心代码，详见洛谷 P3397。

void dfs(ll u,ll fa)
{dep[u]=dep[fa]+1;f[u][0]=fat[u]=fa;for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];for(int i=head[u];i;i=e[i].next){ll v=e[i].to;if(v==fa)continue;dfs(v,u);}
}
ll lca(ll x,ll y)
{if(dep[x]<dep[y])swap(x,y);for(int i=18;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])x=f[x][i];if(x==y)return x;for(int i=18;i>=0;i--){if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
ll dis(ll x,ll y)
{return dep[x]+dep[y]-dep[lca(x,y)]*2;
}

倍增除了求 lca 向上跳之外，在很多题目都会用到倍增思想。

1.洛谷 P1613 跑路

题意

小 A 买了一个空间跑路器，每秒钟可以跑 $2^t$ 千米（$t$ 是任意自然数），可以无限次使用。小 A 的家到公司的路可以看做一个有向图，小 A 家为点 $1$，公司为点 $n$，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证 $1$ 到 $n$ 至少有一条路径。

$2\le n\le 50$，$m\le 10^4$，最优解路径长度 $\le$ LONG_LONG_MAX。

思路

$n$ 的数据范围令人心安，求最短路 Floyd 或者 spfa 随便用。但是这里有个跑路器，所以我们要先处理利用跑路器可以一秒走过的边。

我们同样可以用 Floyd 的思想处理跑路器的影响：设 $di{s}_{u,v}$ 表示 $u$ 到 $v$ 的最短时间，设 $f_{i,j,t}$ 表示，从 $i$ 到 $j$ 是否存在一条长度为 $2^t$ 的最短路径。如果 $\exists f_{i,j,t}=1$，那么 $di{s}_{u,v}=1$；否则 $di{s}_{u,v}=\text{inf}$。

考虑 $f$ 的转移：枚举跑路器参数 $t$ 和一个中间点 $k$（先枚举 $t$ 是要保证 $1\sim t-1$ 已经处理完毕），如果分别 $\exists f_{i,k,t-1}=f_{k,j,t-1}=1$，那么把这两段拼起来，可以用一次 $2^t$ 的跑路器，同时 $di{s}_{i,j}=1$。

最后开心地 Floyd 就好了，答案就是 $di{s}_{1,n}$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=52,M=66,inf=0x3f3f3f3f;
ll n,m;
ll dis[N][N];
bool f[N][N][M];//s到t是否存在2^i路径 
void init()
{for(int t=1;t<=64;t++)for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(f[i][k][t-1]&&f[k][j][t-1])f[i][j][t]=1,dis[i][j]=1;
}
int main()
{memset(dis,inf,sizeof(dis));scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){ll u,v;scanf("%lld%lld",&u,&v);dis[u][v]=1;f[u][v][0]=1;}init();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);printf("%lld",dis[1][n]);return 0;
}

2.洛谷 P4155 国旗计划

题意

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

A 国边境线上设有 $M$ 个边防站，顺时针编号 $1$ 至 $M$。每名边防战士常驻两个边防站，并且善于在这两个边防站之间长途奔袭，我们称这两个边防站之间的路程是这个边防战士的奔袭区间。$N$ 名边防战士都是精心挑选的，身体素质极佳，所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。

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

$N\le 2\times 10^5,M<10^9$

思路

先破环成链。

两个战士可以接力，需要两个战士的区间有交（存在一个点分别属于两个战士的区间）。

处理每个被固定选定的 $n$ 个战士，如果遍历所有战士就去到 $O(n^2)$ 了。那当然要优化处理，肯定是不能一个一个跳的，那么可以尝试倍增。

设 $f_{i,k}$ 表示从战士 $i$ 出发，合法地接力了 $2^k$ 个战士，到达了哪一个边防战士。先 $O(n)$ 处理 $f_{i,0}$，然后传统的倍增操作即可，$O(2n\log 2n)$：

void init()
{ll nxt=1;for(int i=1;i<=nn;i++){while(nxt<=nn&&a[nxt].l<=a[i].r)nxt++;//最远的可以转接 f[i][0]=nxt-1;}for(int i=1;(1<<i)<=n;i++)for(int s=1;s<=nn;s++)f[s][i]=f[f[s][i-1]][i-1];
}

对于每个战士，我们从高到低枚举 $k$ 来跳。对于一个战士 $pos$，如果$r_{pos}\ge l_{start}+m$，就是走完了一圈。最后记得加上自己和闭环的战士就好了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e5+9,M=20;
ll n,nn,m;
struct node
{ll l,r,id;
}a[N];
bool cmp(node x,node y)
{return x.l<y.l;
}
ll f[N][M];
void init()
{ll nxt=1;for(int i=1;i<=nn;i++){while(nxt<=nn&&a[nxt].l<=a[i].r)nxt++;//最远的可以转接 f[i][0]=nxt-1;}for(int i=1;(1<<i)<=n;i++)for(int s=1;s<=nn;s++)f[s][i]=f[f[s][i-1]][i-1];
}
ll ans[N];
void cal(ll x)
{ll tot=1,cur=x;for(int i=M-1;i>=0;i--){ll pos=f[cur][i];if(pos&&a[pos].r<a[x].l+m){cur=pos;tot+=(1<<i);}}ans[a[x].id]=tot+1;//闭环 
} 
int main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++){ll l,r;scanf("%lld%lld",&l,&r);if(r<l)r+=m;a[i]=(node){l,r,i};}sort(a+1,a+n+1,cmp);nn=n;for(int i=1;i<=n;i++){nn++;a[nn].l=a[i].l+m;a[nn].r=a[i].r+m;}init();for(int i=1;i<=n;i++)cal(i);for(int i=1;i<=n;i++)printf("%lld ",ans[i]);return 0;
}