自动搬运

查看原文

来自洛谷，原作者为

	Jerrycyx 尽人事，听天命。个人中心：/problem/U543126

搬运于2025-08-24 22:47:40，当前版本为作者最后更新于2025-02-18 11:46:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

引言

思路上，其它题解已经讲得很清楚了，就是预处理再倍增。但是具体的转移方程和代码实现迄今为止却没有一篇题解讲清楚，导致本蒟蒻狂调一整天。

这里我参考

https://www.luogu.com.cn/article/y8u620q0)里的处理方式，讲一讲相关状态的定义和转移、预处理和倍增的具体过程是怎样的。

前置

名词解释

先解释一下将要用到的名词：

• 元素/点：均指某个人；
• 位置：某一个排行榜内的一个排名；
• 组：一个排行榜；
• 排名高/低：在排行榜内的位置靠前/后。
• 跳/走 $x$ 步：将题目看成“每次可以跳一步，$x$ 可以跳到 $y$ 当且仅当存在一个序列使得 $y$ 出现在 $x$ 后面，问最少跳几步。”（来源）

结构体

首先，定义一个结构体类型 Rank，内含一个大小为 $m$ 的数组，存储的是一个点在各个组内的排名信息、一个点在各个组的可达最高排名/可达范围（每组内都是一段后缀）的起点。

struct Rank{
	int c[M];
};

我们要让它支持两种操作：比较和合并。

先说合并。在预处理过程中，我们会得到某个点通过某种单一路径可以得到不同的最高排名信息。而这些信息需要合并成一个完整的排名信息，即这个点通过所有路径所能到达每组的最高排名。

合并的代码也很简单，直接取各个方式的最高排名即可，本文中重载为加号 +：

Rank operator + (const Rank &x,const Rank &y)
{
	Rank res;
	for(int i=1;i<=m;i++)
		res.c[i]=min(x.c[i],y.c[i]);
	return res;
}
void operator += (Rank &x,const Rank &y){x=x+y;}

（其实这里重载的加号更像是一个 $\min$ 操作？）

再说比较。在倍增过程中，我们要判断某个点 $x$ 是否已经可以一步到达另一个点 $y$。这种情况发生当且仅当 $x$ 所能到达的最高排名中存在一个位于 $y$ 的前面。

bool operator < (const Rank &x,const Rank &y) //x能够一步走到y当且仅当x<y 
{
	for(int i=1;i<=m;i++)
		if(x.c[i]<y.c[i]) return true;
	return false;
}

以上单次操作时间复杂度均为 $O(m)$。

状态表示

然后是倍增的状态表示（姑且先这么叫）。

• $p(i)$ 表示 $i$ 在每一组的原始排名（代码中为 pos）；
• $f(i,j)$ 表示 $i$ 在每一组中的后缀跳 $2^j$ 步后能抵达每一组的最高排名；
• $g(i,j)$ 表示第 $i$ 组内处于 $[j,n]$ 位置上的所有人在每一组的最高排名（即后缀和）。

以上三个状态都是 Rank 类型。

（迄今为止所有题解都没有提到需要用 $g$ 来辅助计算 $f$，导致本蒟蒻迷惑了很久。）

解释：

• $f$ 表示每组后缀是因为，除了第一步是只能从单点走成后缀以外，其它所有步都是 $m$ 段后缀上的所有点尝试向外跳，状态这样设置更好转移。
• $f(i,0)$ 不好直接计算，所以此处 $g$ 的目的便是辅助初始化 $f(i,0)$，具体过程在后面。

特别注意

本题千万不要把不同组内同一个数的来回切换看做一步！

（这个错误想法导致我挂了很多次，甚至写这篇题解时也差点又这么想。）

预处理

$g$ 数组

对于倍增的预处理，首先需要计算 $g$，前面已经提到它是一个后缀和，所以直接这样计算就行，时间复杂度 $O(m^2 n)$。

$$g(i,j) = \sum_{k=j}^{n} p(a_{i,j}) = p(a_{i,j}) + g(i,j+1) $$

（求和符号 $\sum$ 所用为上文重载过的加号，下同。）

for(int i=1;i<=m;i++)
	for(int j=n;j>=1;j--)
	{
		if(j==n) g[i][j]=pos[a[i][j]];
		else g[i][j]=pos[a[i][j]]+g[i][j+1];
	}

$f(i,0)$ 初始化

有了 $g$ 以后就可以据此来初始化 $f(i,0)$ 了，时间复杂度 $O(m^2 n)$。

$$f(i,0) = \sum_{j=1}^{m} g(j,p(i)_j)$$

这里面的 $j$ 用来枚举 $i$ 所属的组。对于某一个 $j$，$p(i)_j$ 表示 $i$ 在第 $j$ 组中所处的位置。根据定义，$f(i,0)$ 表示每一组内 $i$ 的后缀跳 $1$ 步的最高排名。若当前在第 $j$ 组，那么这一段后缀就是 $[p(i)_j,n]$，$g(j,p(i)_j)$ 就表示了这段后缀在所有组上可达的最大排名（走的这 $1$ 步就是将这些最大排名扩展为后缀）。将所有组内的 $m$ 段后缀合并起来得到 $f(i,0)$， 所表示即为 $m$ 段后缀在全局的可达最大排名。

for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		if(j==1) f[i][0]=g[1][pos[i].c[1]];
		else f[i][0]+=g[j][pos[i].c[j]];
	}

剩下的 $f$

最后就可以求出所有 $f$ 值了，时间复杂度 $O(m^2 n \log n)$。

$$f(i,k) = \sum_{j=1}^{m} f(a_{j,f(i,k-1)_j},k-1)$$

该方程中 $j$ 的作用为枚举中转点，我们只需要记录排名最高的那个中转点就行了。

解释一下为什么只用记录最高排名就行了。因为这里方程所转移的只是将这个最高排名点作为中转点，从而便于走到该组内其它点的（以最高点走向组内其它点一定最优）。

反之，若某条路径无需以它作为中转点就可直达，那么这条路径的贡献应该在枚举这个中转点之前就已经计算完毕。如果加上中转点，多出来了一段长度，比已有的路径更劣，也不会更新和影响现有答案。

$f(i,k-1)_j$ 表示 $i$ 对应后缀走 $2^{k-1}$ 步，在第 $j$ 组的最高排名/可达后缀；$a_{j,f(i,k-1)_j}$ 即为这个最高排名所对应的数，令它为 $x$。最后 $f(x,k-1)$ 也就是从点 $x$ 出发，再走 $2^{k-1}$ 步（刚才所得已经是可达后缀了，所以这里无需再走一步来将单点扩展为后缀），一共就是 $2^{k-1}+2^{k-1}=2^k$ 步，即 $f(i,k)$。

for(int k=1;k<=logN;k++) //确定其余 f
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(j==1) f[i][k]=f[a[j][f[i][k-1].c[j]]][k-1];
			else f[i][k]+=f[a[j][f[i][k-1].c[j]]][k-1];
		}

倍增

求解

前面的过程将整个路径分成三部分：

• 第一步，将 $x$ 可达范围从 $m$ 个单点扩展为 $m$ 段后缀；
• 中间若干步，不断扩展使得 $X$ 的表示的后缀中刚好任意一段都不包含 $Y$，这也是倍增过程所求的；
• 最后一步，因为 $X$ 刚好不能达到 $Y$，所以走这最后一步就可以直接抵达 $y$ 了。

读入 $x$、$y$ 后，我们首先需要获取它们的原始排名，设为 $X$ 和 $Y$，第一步以后它们就将成为多段后缀段。

倒序枚举 $k$ 的同时，模拟 $X$ 走 $2^k$ 步后的结果 $nxt$，如果 $nxt<Y$（之前已经重载了 < 符号，表示能够直接抵达）不成立，则把这一步实实在在走出去，令 $X \gets nxt$，并把步数加上 $2^k$。

最后的步数应该加上前后省略的那两步，时间复杂度 $O(m^2 q \log n)$。

无解

对于每一个有效步，至少能多覆盖一个点，否则未来永远无法覆盖更多点了。

因此，一个全部由有效步构成的路径至多有 $n$ 步。超出 $n$ 步代表有效路径无法覆盖 $y$，因此可判无解。

或者你也可以将题目看做图论最短路，$x$ 到 $y$ 至多 $n$ 个点。

特判

注意特判 $x$ 能够一步到达 $y$ 的情况，此时第一步和最后一步是同一步，而中间的步骤根本不存在（因为 $x \neq y$，所以答案至少是 $1$）。

倍增部分代码：

int px,py; scanf("%d%d",&px,&py);
Rank x=pos[px],y=pos[py];
if(x<y) printf("1\n"); //特判一步即达 
else
{
	int ans=0;
	for(int i=logN;i>=0;i--)
	{
		Rank nxt=x;
		for(int j=1;j<=m;j++)
			nxt+=f[a[j][x.c[j]]][i];
		if(!(nxt<y)) ans+=1<<i,x=nxt; //nxt不能抵达y 
	}
	if(ans>n) printf("-1\n"); //无解 
	else printf("%d\n",ans+2);
}

代码

总时间复杂度 $O(m^2 (n+q) \log n)$

提交记录：R203561810。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+5,M=10,logN=17;
int n,m,q,a[M][N];

struct Rank{
	int c[M];
}pos[N],f[N][logN+5],g[M][N];
/*
 * pos[i]：i在每组内的排名/一步后的可达后缀 
 * f[i][j]：i跳2^j步后在每一组的最高排名/可达后缀 
 * g[i][j]：第i组内j~n位置上的所有人在每一组的最高排名/可达后缀 
 */
bool operator < (const Rank &x,const Rank &y) //x能够走到y当且仅当x<y 
{
	for(int i=1;i<=m;i++)
		if(x.c[i]<y.c[i]) return true;
	return false;
}
Rank operator + (const Rank &x,const Rank &y) //合并两个排名信息 
{
	Rank res;
	for(int i=1;i<=m;i++)
		res.c[i]=min(x.c[i],y.c[i]);
	return res;
}
void operator += (Rank &x,const Rank &y){x=x+y;}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			pos[a[i][j]].c[i]=j;
		}
	for(int i=1;i<=m;i++)
		for(int j=n;j>=1;j--) //确定 g 
		{
			if(j==n) g[i][j]=pos[a[i][j]];
			else g[i][j]=pos[a[i][j]]+g[i][j+1];
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) //确定 f[i][0] 
		{
			if(j==1) f[i][0]=g[1][pos[i].c[1]];
			else f[i][0]+=g[j][pos[i].c[j]];
		}
	for(int k=1;k<=logN;k++) //确定其余 f
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
			{
				if(j==1) f[i][k]=f[a[j][f[i][k-1].c[j]]][k-1];
				else f[i][k]+=f[a[j][f[i][k-1].c[j]]][k-1];
			}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int px,py; scanf("%d%d",&px,&py);
		Rank x=pos[px],y=pos[py];
		if(x<y) printf("1\n"); //特判一步即达 
		else
		{
			int ans=0;
			for(int i=logN;i>=0;i--)
			{
				Rank nxt=x;
				for(int j=1;j<=m;j++)
					nxt+=f[a[j][x.c[j]]][i];
				if(!(nxt<y)) ans+=1<<i,x=nxt; //nxt不能抵达y 
			}
			if(ans>n) printf("-1\n"); //无解 
			else printf("%d\n",ans+2);
		}
	}
	return 0;
}

后记

本人蒟蒻，即使知道了倍增思路以后也难以打出代码，最后因为被 $O(m^2(n+q) \log n)$ 的时空复杂度卡得 MLE+TLE 而选择放弃原有的处理方式而学习题解中的处理方式。花费 $30$ min 终于（自认为）读懂。于是打算补充大佬们不屑于讲解和证明的部分，写成此篇题解造福后人。

但是，在写题解的过程中，我发现我的理解依然有诸多缺漏，状态的定义和转移仍有许多不完整甚至错误之处，所以这篇题解也经过多次修正，直到整个逻辑自洽，这整个过程也让我受益匪浅。

因为多次修改，本题解难免会有一些前后语言表述不通顺的情况，还请多多包涵、提出意见，谢谢！