# CF 1372 C. Omkar and Baseball

:::info
[Link](https://codeforces.com/problemset/problem/1372/C)
:::

:::spoiler 目錄
[toc]
:::

## 題意

給定一個$1\sim n$排列的數列，若按照以下交換規則，請問**最少**要交換幾次才能將此數列按升序排列。
交換規則：
從原序列$B$中取一個連續子區間$A$，則在對$A$進行交換後，$A$中的每個元素的**交換後位置**都必須與**交換前位置**不同。
例如：
$B=[1, 2, 3, 4, 5]$，對$A=[2, 3, 4]$交換，則$B=[1, 4, 2, 3, 5]$是一組合法的交換；$B=[1, 4, 3, 2, 5]$則是不合法的交換，因為$B[3]=A[2]=3$位置沒有變動

## 官解

>> 懶得讀XD因為直接看code發現思路差不多，而且實作方法也沒有好多少
>> 另外也在上網翻解答的過程中發現了一個很有趣的組合數學問題：[錯排問題](https://zh.wikipedia.org/zh-tw/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98#%E9%80%92%E6%8E%A8%E6%95%B0%E5%88%97%E6%B3%95)

### 思路

>> 這邊放的是我去翻submission發現很帥的做法改寫而成的

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

int a[200050];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] != i && a[i - 1] == i - 1) {
            ++res;
        }
    }
    
    if (!res) {
        cout << "0\n";
    } else if (res == 1) {
        cout << "1\n";
    } else {
        cout << "2\n";
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

### code

## 初見解

### 思路

因為題目的數列是$1\sim n$剛好各出現一次的數列，因此可以對於數列$A$，排序完成的狀態表示下式成立：
$$
\forall i\in A, A[i]=i
$$
此時假設$A$中存在一個連續區間$S$，滿足以下性質：
$$
\forall j\in S, S[j]\ne j
$$
換句話說就是每個元素都不在其排序後應該在的位置上。
這時可以發現因為所有數都不在位置上，所以$S$一次交換就可以完成排序。

而此時重新假設$A$中存在多個性質區間$S$：$S_1, S_2, \cdots, S_n$，但這些區間都被"在正確位置上的元素"隔開，所以$A$的情況如下描述：
$$
[S_1, b_1, S_2, b_2, \cdots, b_{n-1}, S_n]
$$
且設$b$的索引為$i$，$A[i_n]=b_n, b_n = i_n$。

這時候可以發現，因為$S$中的元素必定不會在正確位置上，所以可以一次交換就直達正確位置；而$b$因為已經在正確位置上了，所以不能一次完成，但可以先交換一次使整個$A$都變成$S$，然後就可以再一次交換完成。

因此答案只會有$[0, 1, 2]$三種，分別代表$A$中沒有$S$、$A$中恰有一$S$、$A$中有多個$S$。只要照這些條件檢查一遍，可在$O{(n)}$求解

### code

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

using namespace std;

int a[200050];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    
    int p1, p2;
    for (p1 = 1; p1 <= n; ++p1)
        if (a[p1] != p1) break;
    for (p2 = n; p2 >= 1; --p2)
        if (a[p2] != p2) break;
    
    if (p2 == 0) {
        cout << "0\n";
        return;
    }
    
    for (int i = p1; i <= p2; ++i) {
        if (a[i] == i) {
            cout << "2\n";
            return;
        }
    }
    cout << "1\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

###### tags: `每日CF梗題挑戰`