【题解】CF2086C Disappearing Permutation

洛谷题解

修复时 \(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;
}