Atcoder 123D Yet Another Sorting Problem

Problem Statement

Given is a sequence pp of length N+MN+M, which is a permutation of (1,2…,N+M)(1,2…,N+M). The ii-th term of pp is pipi.

You can do the following Operation any number of times.

Operation: Choose an integer nn between 11 and NN (inclusive), and an integer mm between 11 and MM (inclusive). Then, swap pnpn and pN+mpN+m.

Find the minimum number of Operations needed to sort pp in ascending order. We can prove that it is possible to sort pp in ascending order under the Constraints of this problem.

Constraints

All values in input are integers.
1≤N,M≤1051≤N,M≤105
1≤pi≤N+M1≤pi≤N+M
pp is a permutation of (1,2…,N+M)(1,2…,N+M).

Input

Input is given from Standard Input in the following format:

NN MM
p1p1 ⋯⋯ pN+MpN+M

Output

Print the minimum number of Operations needed to sort pp in ascending order.

Sample Input 1 Copy

Copy

2 3
1 4 2 5 3

Sample Output 1 Copy

Copy

Sample Input 2 Copy

Copy

5 7
9 7 12 6 1 11 2 10 3 8 4 5

Sample Output 2 Copy

Copy

题目翻译

给定一个长度为 $N + M $ 的排列。

你每次可以选择前 (N) 个数中的一个以及后 $M $ 个数中的一个并将它们交换。

你需要求出，至少需要多少次交换操作才能使得排列变为 (1,2,3,⋯,N + M)。

题目解析

首先假设位置小于(N)的为左边，([N+1,N+M])为右边

如果可以交换同一边的数字，那么只要(i)向(a_i)连边，每个大小为(S)的连通块都能通过(S-1)次操作完成交换。令连通块数量为(K),操作次数为(N+M-K)

考虑到只有不同边的数字能交换的限制，按上述方式建图，如果一个联通块同时包括左边和右边的数字，则仍然可以通过(S-1)次还原。

如果连通块只包含左边或者右边的数字，设只属于左边的连通块数量为(X),只属于右边的连通块数量为(Y)。只要那(X)个连通块和(Y)个连通块任意交换一个数字，就可以满足连通块同时包含左边和右边数字的条件

最后答案为(N+M-K+2*max(X,Y))

联通块维护并查集即可

注意：需要考虑连通块只有1个的情况，即(i)一开始就位于目标位置，不需要与其他联通块交换。不能算在(X)和(Y)个单边联通块里面

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int n,m,set[200005],cntL[200005],cntR[200005],a[200005];
int find(int x){
    if (set[x]==x) return x;
    return set[x]=find(set[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n+m;i++){
        scanf("%d",&a[i]);
        set[i]=i;
        if (i<=n) cntL[i]=1;
        else cntR[i]=1;
    }
    for (int i=1;i<=n+m;i++){
        int x=find(i),y=find(a[i]);
        if (x!=y) {
            set[x]=y;
            cntL[y]+=cntL[x];
            cntR[y]+=cntR[x];
        }
    }
    int x=0,y=0,k=0;
    for (int i=1;i<=n+m;i++){
        if (find(i)==i) {
            k++;
            if (cntL[i]+cntR[i]==1) continue;//自己位置不需要交换
            if (cntL[i]==0) x++;
            if (cntR[i]==0) y++;
        }
    }
    cout<<n+m-k+2*max(x,y)<<endl;
}