喵~ 主人好呀！今天我们来解决一道关于排列的有趣问题：Omkar and Baseball。这道题就像整理一团乱糟糟的毛线球，只要找到窍门，一下子就能理顺啦，喵~

题目大意

帕特里克（Patrick）玩棒球玩得头昏脑胀，他记得自己的得分记录应该是完美的 1, 2, 3, ..., n，但是现在却发现数字全都乱了套！

我们可以进行一种叫做 “特殊交换” 的操作：

1. 选取数组中的任意一个 连续子数组。
2. 对这个子数组中的元素进行重新排列。
3. 排列后，子数组中的 任何一个元素都不能回到它在操作前所在的位置。

举个栗子：对 [1, 2, 3] 进行特殊交换，可以得到 [3, 1, 2]（1 不在原位，2 不在原位，3 也不在原位），但不能得到 [3, 2, 1]，因为 2 还待在它原来的位置上，这是不被允许的喵！

我们的任务是，给定一个 1 到 n 的乱序排列，计算最少需要多少次“特殊交换”才能让它变回 1, 2, 3, ..., n 的有序状态。

---

题解方法

这个问题看起来可能有点复杂，但其实只要我们仔细分析，就会发现答案只有三种可能：0、1 或 2。我们可以像小猫探路一样，一步步分析，喵~

情况一：0 次交换

这是最简单的情况啦！如果给定的数组已经是 1, 2, 3, ..., n 的有序状态，那我们什么都不用做，答案自然就是 0 啦。就像一排小鱼干已经摆得整整齐齐，我们舔舔爪子看着就好，喵~

情况二：1 次交换

什么时候我们能用一次操作就解决问题呢？

首先，我们要找到所有“不乖”的元素，也就是那些没有待在自己正确位置上的元素（a[i] != i+1）。这些不乖的元素会形成一个或多个“混乱”的区域。但是，由于我们的操作对象是 连续子数组，所以我们只能选择一个包含 所有 不乖元素的、从最左边第一个不乖的元素到最右边最后一个不乖的元素的连续区域 a[l...r] 进行操作。

比如 [1, 4, 3, 2, 5]，不乖的元素是 4, 3, 2，它们组成的连续区域就是 a[1...3]。

现在的问题是，我们能对 a[l...r] 进行“特殊交换”来把它排好序吗？ “特殊交换”的规则是：子数组里没有一个元素能留在原位。 而我们的目标是：把这个子数组排好序，也就是让数字 i+1 最终都到 a[i] 的位置上。

结合起来看，只要在 a[l...r] 这个混乱区域内，每一个元素 都处在错误的位置上（即对于所有 i 从 l 到 r，都有 a[i] != i+1），我们就可以通过一次特殊交换把它们全部归位！因为没有任何一个元素本来就在它的目标位置上，所以“不能留在原位”的规则就不会和“把它们放到正确位置”的目标冲突。

总结一下，如果数组不是有序的，但所有不在正确位置的元素形成了一个连续的块，并且这个块里面 没有 任何一个元素恰好在它应该在的位置上，那么答案就是 1。

情况三：2 次交换

那如果情况比上面更复杂呢？

如果那个从 l 到 r 的混乱区域内部，竟然藏着一个“乖宝宝”元素呢？也就是说，存在一个 i (l <= i <= r)，使得 a[i] == i+1。

例如 [3, 2, 4, 5, 1, 6, 7]。

• a[0]=3 (错位), a[1]=2 (正确), a[2]=4 (错位), a[3]=5 (错位), a[4]=1 (错位)。
• 最左边的错位是 a[0]，最右边的是 a[4]。所以我们的混乱区域是 a[0...4]，也就是 [3, 2, 4, 5, 1]。
• 但是看，a[1]=2，这个 2 恰好就在它应该在的位置上！

这时候，我们就不能用一次操作搞定了。因为“特殊交换”要求我们必须把 a[1] 的 2 移走，可要排好序又要求 2 必须待在 a[1]。这就矛盾了呀，喵！

怎么办呢？我们可以用两次操作来解决！

1. 第一次交换：对整个混乱区域 a[l...r] 进行一次特殊交换。这次我们的目的不是排序，而是 打破所有内部的正确位置。比如，我们可以把这个区域里的所有元素循环移动一位，这样原来位置正确的元素就肯定跑到错误的位置上去了。操作完后，我们就得到了一个新的混乱区域，这个区域满足了“情况二”的条件（内部没有任何元素在正确位置上）。
2. 第二次交换：对新的混乱区域再进行一次特殊交换，这次就能成功地将它完全排好序了。

所以，只要混乱区域内部存在哪怕一个位置正确的元素，答案就是 2。

而且，可以证明，我们总能用最多两次操作解决问题，所以不需要考虑比 2 更大的情况啦。

---

题解

根据上面的分析，我们可以写出代码了，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 1. 从左边开始，找到第一个不在正确位置的元素
    int l = 0;
    while (l < n && a[l] == l + 1) {
        l++;
    }

    // 如果 l 走到了尽头，说明整个数组都是有序的
    if (l == n) {
        std::cout << 0 << "\n";
        return;
    }

    // 2. 从右边开始，找到第一个不在正确位置的元素
    int r = n - 1;
    while (r >= 0 && a[r] == r + 1) {
        r--;
    }

    // 3. 检查 [l, r] 这个混乱区域内部，有没有“乖宝宝”元素
    bool has_fixed_point_in_middle = false;
    for (int i = l; i <= r; ++i) {
        if (a[i] == i + 1) {
            has_fixed_point_in_middle = true;
            break; // 只要找到一个就够了喵
        }
    }

    // 4. 根据检查结果输出答案
    if (has_fixed_point_in_middle) {
        std::cout << 2 << "\n"; // 有乖宝宝，需要2次
    } else {
        std::cout << 1 << "\n"; // 全是坏孩子，1次就够
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码解释：

1. l 指针：int l = 0; while (l < n && a[l] == l + 1) { l++; }
   • 这就像一只小猫从左边开始悄悄地走，喵~ 只要它看到 a[i] 的位置上就是数字 i+1 (也就是放对了)，它就继续往前走。当它停下来时，就找到了第一个“不乖”的元素的位置 l。
2. 判断是否已有序：if (l == n)
   • 如果小猫 l 一路走到了数组末尾都没停下，说明整个数组都是整整齐齐的，那就什么都不用做，输出 0。
3. r 指针：int r = n - 1; while (r >= 0 && a[r] == r + 1) { r--; }
   • 另一只小猫 r 从右边倒着走，同样是寻找第一个不乖的元素。这样，l 和 r 就圈定了那个需要我们关注的“混乱区域” [l, r]。
4. 检查混乱区域：for (int i = l; i <= r; ++i) { ... }
   • 现在我们就要仔细检查 [l, r] 这个区域了。这个循环就是看看这个区域里有没有“身在曹营心在汉”的乖宝宝 (也就是 a[i] == i+1 的元素)。
5. 输出结果：
   • 如果 has_fixed_point_in_middle 变成了 true，说明找到了这样的乖宝宝，情况有点复杂，需要两次操作才能摆平，答案就是 2 喵。
   • 如果循环结束了 has_fixed_point_in_middle 还是 false，说明这个混乱区域里一个乖宝宝都没有，大家全都站错了位置，那我们就可以一次性把它们全部归位！答案就是 1 喵~

---

知识点介绍

• 排列 (Permutation)：一个排列是指将一组对象进行有顺序的安排。在这道题里，就是把数字 1 到 n 按某种顺序排列。
• 子数组 (Subarray)：数组中一段连续的元素序列。这是本题操作的基本单位，理解它的“连续”性很重要。
• 分类讨论 (Case Analysis)：这是算法竞赛中一种非常强大且常见的思维方式！当一个问题看起来有很多可能性时，我们可以尝试根据某些关键特征将其分解为几个简单、互斥的子情况来分别处理。就像这道题，我们把它分成了“0次”、“1次”、“2次”三种情况，问题一下就清晰了，喵~

希望这篇题解能帮到主人哦~ 如果还有不明白的地方，随时可以再来问我，喵~❤️