题解：AT_abc436_e [ABC436E] Minimum Swap

· · 题解

赛时卡了 20min 来写篇题解。

我们将 i\rightarrow P_i 连一条有向边，由于 P 是个排列，因此我们最终会连出若干个环，我们的目标就是让所有 P_i=i 也就是只存在自环。

每次操作相当于使 i\rightarrow P_j 并使 j\rightarrow P_i。

考虑在这种情况下每次操作会带来什么贡献。

  1. 若操作的 P_i,P_j 在同一环内，则我们发现这次操作会把这个环拆成两个环，造成了 1 的贡献。
  2. 若操作的 P_i,P_j 不在同一环内，则本次操作会合并两个环，造成 -1 的贡献。

我们显然希望环的数量最多，因此只有 1 类操作是有价值的，因此我们相当于统计不同的 1 类操作的个数。

那么就很好计数了，任意环内的任意点对均为合法操作，因此我们设 sz_i 为环 i 的大小，答案即为：

\displaystyle \sum \frac{sz_i\times(sz_i-1)}{2}

简单用并查集维护连通块即可。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
const int N=3e5+5;
int p[N],n,cnt,sum,id[N],f[N],sz[N];
ll ans;
int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);}
void hb(int x,int y){
    if(gf(x)==gf(y))return;
    sz[gf(y)]+=sz[gf(x)];
    f[gf(x)]=gf(y);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&p[i]),id[p[i]]=i,sz[i]=1,f[i]=i;
    for(int i=1;i<=n;++i){
        if(p[i]==i)continue;
        hb(p[i],i);
    }
    for(int i=1;i<=n;++i)
        if(f[i]==i)ans+=1ll*sz[i]*(sz[i]-1)/2;
    printf("%lld",ans);
    return 0;
}

::::