AT_abc371_g

场上 20min 过了。感觉现有题解对复杂度分析有点问题，于是写一写。

首先置换的形状显然是若干个环。考虑设操作次数为 $k$，依次对每个环贪心。对于一个长为 $l$ 的环 $i$，在满足限制的情况下，贪心地把 $a$ 中更小的放到前面。设在这种情况下要求 $k\bmod l=f_i$。

考虑这个环的操作对于其他环的操作有什么限制。若后面有另一个长为 $l'$ 的环 $j$。若 $\gcd(l,l')=1$ 则显然没有限制。否则，若存在 $d|l,d|l'$，则会有限制：$f_i\bmod d=f_j\bmod d$。

于是找到 $l$ 的所有因数后，会得到若干个形如 $f_j\bmod x=y$ 的限制。这个理论上可以 excrt，但是不难发现 $f_i<l_i,\sum l_i=n$，所以可以每次暴力地找合法的 $f_i$，精细实现，这一部分的复杂度就是 $O(n)$ 的。处理完当前环的 $f_j$ 后，再枚举 $l'$ 的因数，更新限制即可。

这个复杂度看似是 $O(n\sqrt n+nd(n)\log n)$ 的（中间要进行取 $\operatorname{lcm}$ 的操作），但是发现所有环长之和为 $n$，对于每个环的复杂度又是 $O(\sqrt l+d(l)\log l)$ 的，不难发现 $\forall l,l=1$ 时复杂度最大，为 $O(n)$。

code：

int n,m,a[N],p[N],to[N],ans[N],lim[N];
bool vis[N];
vector<int> g,h;
void dfs(int u){
	vis[u]=1;
	g.eb(a[u]);
	h.eb(u);
	if(!vis[to[u]]){
		dfs(to[u]);
	}
}
void Yorushika(){
	read(n);
	rep(i,1,n){
		read(p[i]);
		to[p[i]]=i;
	}
	rep(i,1,n){
		read(a[i]);
	}
	mems(lim,-1);
	rep(i,1,n){
		if(!vis[i]){
			g.clear(),h.clear();
			dfs(i);
			int p=0,d=0,x=1;
			for(int j=1;j*j<=g.size();j++){
				if(g.size()%j==0){
					if(~lim[j]){
						while(d<(int)g.size()&&d%j!=lim[j]){
							d+=x;
						}
						x=lcm(x,j);
					}
					int k=g.size()/j;
					if(~lim[k]){
						while(d<(int)g.size()&&d%k!=lim[k]){
							d+=x;
						}
						x=lcm(x,k);
					}
				}
			}
			p=d;
			for(int j=d;j<(int)g.size();j+=x){
				if(g[j]<g[p]){
					p=j;
				}
			}
			rep(j,0,(int)g.size()-1){
				ans[h[j]]=g[(j+p)%(int)g.size()];
			}
			for(int j=1;j*j<=g.size();j++){
				if(g.size()%j==0){
					int k=g.size()/j;
					lim[j]=p%j,lim[k]=p%k;
				}
			}
		}
	}
	rep(i,1,n){
		printf("%d ",ans[i]);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}