自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:55:40，当前版本为作者最后更新于2024-03-09 22:22:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

很深刻的题。

图上行走问题自然想到倍增，先简单尝试一下。

记 $f_{i,j,k}$ 表示日期 $\bmod T_i=k$，从 $i$ 走 $2^j$ 步到的节点。

但发现走 $2^j$ 步的过程中，可能走到 $T_u\gt T_i$ 的点，这样只记录日期 $\bmod T_i$ 的信息就不够了。

所以如果遇到了点 $u$，我们将 $f_{i,j,k}$ 强制停止在点 $u$，需要记录 $g_{i,j,k}$ 表示实际行走的长度。

我们称 $T_i$ 相同的点为同一层的点，考虑这样对于每次询问的复杂度，每一步有 2 种可能，如果强制停止了，那么层数加 $1$，否则剩余距离减半。

记 $m=\max T_i,N=\sum T_i$，每次减半前最多爬 $\log m$ 层，一次询问的复杂度为 $O(\log m\log V)$。

但是我们预处理时同样要这样走，所以总时间复杂度为 $O(N\log^2 V\log m)$，无法通过。

发现实际上我们记录这个 $2^j$ 步并没有什么意义，因为我们可能根本走不到 $2^j$ 步就强制停止了，而这个步数的要求却使得我们有较高的复杂度。

因为只有走到了，$T_u\gt T_i$ 的点 $u$ 才会强制停止，我们干脆把 $f_{i,j,k}$ 定义为，从 $i$ 走 $2^j$ 个同一层的点后到达的点，这里同样会强制停止，但是我们的预处理的复杂度变成 $O(N(\log m+\log V))$。

再来考虑询问，我们先用 $O(\log m)$ 的复杂度爬到最高层，再用 $O(\log V)$ 的复杂度找到这一层的最后一个节点，然后层数上限减 1，总复杂度 $O(\log m(\log m+log V))$。

这样，我们以 $O(N(\log m+\log V)+Q\log m(\log m+log V))$ 的复杂度解决了本题。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=2e18;
const int N=1e5+5;
int n,q,t[N],mx;
int *c[N],*f[61][N];
ll *g[61][N];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&t[i]);
		c[i]=new int[t[i]];
		mx=max(mx,t[i]);
		for(int j=0;j<=60;++j)f[j][i]=new int[t[i]],g[j][i]=new ll[t[i]];
	}
	for(int i=1;i<=n;++i)
		for(int j=0;j<t[i];++j)scanf("%d",&c[i][j]);
	for(int j=1;j<=mx;j<<=1){
		for(int i=1;i<=n;++i)if(t[i]==j)for(int k=0;k<j;++k){
			int x=c[i][k];ll dt=1;
			while(t[x]<j&&dt<inf){
				int y=f[60][x][k+dt&t[x]-1];
				dt+=g[60][x][k+dt&t[x]-1];
				x=y;
			}
			f[0][i][k]=x,g[0][i][k]=min(inf,dt);
		}
		for(int l=1;l<=60;++l)for(int i=1;i<=n;++i)if(t[i]==j)for(int k=0;k<j;++k){
			int x=f[l-1][i][k];ll dt=g[l-1][i][k];
			if(t[x]!=j){
				f[l][i][k]=x;
				g[l][i][k]=dt;
				continue;
			}
			f[l][i][k]=f[l-1][x][k+dt&j-1];
			g[l][i][k]=min(inf,g[l-1][x][k+dt&j-1]+dt);
		}
	}
	while(q--){
		int x;ll T,dt,w;
		scanf("%d%lld%lld",&x,&T,&dt);
		while(dt){
			for(int j=60;~j&&dt;--j)if((w=g[j][x][T&t[x]-1])<=dt){
				dt-=w;
				int ls=t[x];
				x=f[j][x][T&t[x]-1];
				T+=w;
				if(t[x]!=ls)j=61;
			}
			if(dt){
				x=c[x][T&t[x]-1];
				++T,--dt;
			}
		}
		printf("%d\n",x);
	}
	return 0;
}