修复时 \(a_i\) 必须要用掉 \(i\),此时就要对原先放 \(i\) 的位置修复,于是又要用掉一个数,又要再修一个点,如此循环往复直到这次修复需要的数恰好是被吃掉的(形成环),显然修复次数就是环的长度,直接循环计算即可。可以发现这一轮修过的点下一轮肯定还要修,如果下一轮被吃掉的点恰好是之前修过的,就没有代价;如果是没修过的,那就从当前点开始循环修一遍。每个点修过之后就记录一下,下次就不用修了,时间复杂度就是 \(O(n)\),答案显然是把当前置零的点修完之后记录下来的点的数量。
#include <bits/stdc++.h>
#define mem(a,v) memset(a,v,sizeof(a))
#define endl '\n'
#define FILE(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
#define pii pair<int,int>
#define pll pair<long long,long long>
#define st first
#define nd second
#define pb push_back
using namespace std;
using ll=long long;
using lld=long double;
const int N=1e5+10;
const ll mod=1000000007;
int T,n,k,a[N],id[N];
ll ans;
bool vis[N];
void solve(){ans=0,mem(vis,0),cin>>n;for(int i=1;i<=n;i++)cin>>a[i],id[a[i]]=i;for(int i=1,b;i<=n;i++){for(cin>>b;!vis[b];b=id[b])vis[b]=true,ans++;cout<<ans<<' ';}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);for(cin>>T;T--;cout<<endl)solve();return 0;
}