题解：AT_arc124_d [ARC124D] Yet Another Sorting Problem

Elairin176 · 2025-01-28 10:41:54 · 题解

Link
比较套路。

解法

看到排列，我们直接考虑 i 向 p_i 连边。

注：如果我们这样建边，那么我们容易证明连出来的图由若干个孤立点和环组成。并且，环的点数和边数一致。利用这些性质可以方便地解题。

那么，一次交换操作实际上就对应着图上的两条边 (u_1,v_1),(u_2,v_2) 变为 (u_1,v_2),(u_2,v_1)。
我们给对应的点染上色，并记环的点数为 size，分为以下几种情况讨论：

• 孤立点。这种情况无需考虑，因为已经在正确的位置上了。
• 异色环。（环上两种颜色的点均存在）这时我们易证操作次数最少为 size-1。（总能保留一对异色点）
• 同色环。（环上结点同色）这时如果我们直接交换那么操作次数是 size+1 的。但是我们注意到，如果将一对异色的同色环同时操作，那么操作次数就变成了这两个环的 size 之和。所以这时我们的策略如下：导出所有的黑白同色环，贪心地选取 size 大的环合并，剩下的环直接交换。

CODE：

//luogu paste jo5j6ogx
cst int N=2e5;
int n,m,last[N+10],tot,p[N+10];
bool col[N+10];
struct edge{
    int u,nxt;
}a[N+10];
il void add(int u,int v){
    a[++tot].u=v;
    a[tot].nxt=last[u];
    last[u]=tot;
}
int siz[N+10],sum[N+10],cnt,ans;
vector<int>vec[2];
bool vis[N+10];
il void dfs(int u){
    if(vis[u]) ret;
    vis[u]=1;
    sum[cnt]+=col[u];siz[cnt]++;
    for(int i=last[u];i;i=a[i].nxt){
        int v=a[i].u;
        dfs(v);
    }
}
int main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    n=read<int>();m=read<int>();
    for(int i=1;i<=n+m;i++){
        p[i]=read<int>();
        add(i,p[i]);
        col[i]=(i>n);
    }
    for(int i=1;i<=n+m;i++){
        if(vis[i]) continue;
        cnt++;dfs(i);
        if(siz[cnt]==1) continue;
        if(sum[cnt]==0) vec[0].emplace_back(siz[cnt]);
        else if(sum[cnt]==siz[cnt]) vec[1].emplace_back(siz[cnt]);
        else ans+=siz[cnt]-1;
    }
    sort(vec[0].begin(),vec[0].end(),[](cst int&x,cst int&y){ret x>y;});
    sort(vec[1].begin(),vec[1].end(),[](cst int&x,cst int&y){ret x>y;});
    int s0=vec[0].size(),s1=vec[1].size(),p0,p1;
    for(p0=0,p1=0;p0<s0&&p1<s1;p0++,p1++) ans+=vec[0][p0]+vec[1][p1];
    for(;p0<s0;p0++) ans+=vec[0][p0]+1;
    for(;p1<s1;p1++) ans+=vec[1][p1]+1;
    write(ans);
    ret 0;
}

Record(Atcoder)