如题。

题解区全部都是“玄学”的暴力做法，但我分析是可以卡到 $O(n^2)$ 的。

比如这么一份代码：

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e5+5;
int n,k,t[mxn],l,v[mxn],b[mxn],m[mxn];
int main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;++i)cin>>t[i];
	for(int i=1;i<=k;++i)cin>>v[i];
	for(int i=1;i<=k;++i)cin>>b[i];
	for(int i=1;i<=k;++i){
		l=0;//注意！此处去掉了强制在线，和时间复杂度无关！把这行删掉就可以强制在线，是原题
		v[i]=(v[i]+l-1)%n+1;l=0;
		for(;m[v[i]]<b[i];){
			if(m[v[i]]==0)++l;
			m[v[i]]=b[i]--;
			v[i]=t[v[i]];
		}
		cout<<l<<' '<<cnt<<'\n';
	}
}

通过下面这份 generator 就可以卡到 $O(n^2)$：

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("b.in","w",stdout);
	int n=100000;
	cout<<n<<' '<<n<<'\n';
	for(int i=1;i<=n;++i)cout<<i%n+1<<' ';cout<<'\n';
	for(int i=1;i<=n;++i)cout<<i<<' ';cout<<'\n';
	for(int i=1;i<=n;++i)cout<<1<<' ';cout<<'\n';
}

但神奇的是我本机居然 0.2s 跑过了！

然后我开始合理怀疑是编译器优化掉了。

我们对源代码这么改一下：

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e5+5;
int n,k,t[mxn],l,v[mxn],b[mxn],m[mxn];
int main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;++i)cin>>t[i];
	for(int i=1;i<=k;++i)cin>>v[i];
	for(int i=1;i<=k;++i)cin>>b[i];
	int cnt=0;
	for(int i=1;i<=k;++i){
		l=0;//注意！此处去掉了强制在线，和时间复杂度无关！
		v[i]=(v[i]+l-1)%n+1;l=0;
		for(;m[v[i]]<b[i];){
			if(m[v[i]]==0)++l;
			m[v[i]]=b[i]--;
			v[i]=t[v[i]];
			++cnt;
		}
		cout<<l<<' '<<cnt<<'\n';
	}
}

实际上就是加了个计数器，统计总共跳了多少次for

而这次它就跑了2s+，通过输出的 $cnt$ 也可以看出是真的跑了 $O(n^2)$。

所以这题正解真的是这么暴力跑吗？