Codeforces Round #842 (Div. 2) Problem D - Lucky Permutation

1.例子序列：1 5 6 2 4 3
2.根据 i 指向 p[i]建图，我们能得到三个集合
(1): 1 - 1
(2): 2 - 5 - 4 - 2
(3): 3 - 6 - 3
ps:
将一个排列恢复成递增序列的最小操作次数：
POJ 1674

for (int i = 1; i <= n; i++)
{
    while (a[i] != i)
    {
        swap(a[i], a[a[i]]);
        ans++;
    }
}

如果要让一个集合回到递增的顺序，那么(1)执行（1-1=0）步，（2）执行（3 - 1 = 2）步…
同理，（假定集合中的元素个数为s个）我们发现一个集合中的元素都能回到自己的位置，并且全部回到自己位置的交换操作次数为(s - 1)。

题目要求我们最后结果包含一个有逆序对：1 2 3 4 5 6 … 我们能发现，只有仅仅交换一对相邻元素是才会只有一组逆序对
1 2 3 4 6 5
1 2 3 5 4 6 …
同时看上面的例子，我们对集合（2）进行操作：如果我们只交换2 - 4 ，那么就直接构成了一堆逆序对（5,4），同时2还回到了正确位置。

所以总结：
1.我们称一个集合为一个置换环，让每个置换环成为递增序列的交换次数为 （s - 1）次（s为元素个数）。
2.根据题目要求如果置换环中存在相邻元素，那么操作(s - 2)次即可（我们只要一对逆序对，所以只能挑选一个符合要求的置换环进行操作）
3.一个环（s1 - 1),所有环（s1 + s2 + … + sn）-(n) = N(总元素数) - n(环的数量)
4.如果存在一个置换环中存在相邻元素: ans = N - n - 1;
否则我们要先全部排好序后，再交换一对相邻元素 ans = N - n + 1;

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 2e5 + 10;
const int R = (1 << 20) + 10;
const int Base = N / 2;
const int M = 2 * N;
const int P = 998244353;
typedef pair<int, int> PII;
typedef long long LL;
int n, m;
const LL mod = 1e9 + 7;
int a[N];
bool st[N]; // 记录已经搜过的环的点
int v[N];   // 记录每个置换环中，已经出现过的点
map<int, int> g;
bool f = false;
void dfs(int u)
{
    st[u] = true;
    if (v[u]) // 防止死循环
    {
        return;
    }
    v[u] = 1;
    if (v[u - 1] || v[u + 1]) // 判断是否存在相邻元素
    {
        f = true;
    }
    dfs(g[u]);
    v[u] = 0; // 不想memset，就最后复原了
}

void solve()
{
    scanf("%d", &n);
    g.clear();
    f = false;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        st[i] = 0; // 记得初始化
    }

    for (int i = 1; i <= n; i++)
    {
        g[i] = a[i]; // 建图
    }
    int cur = 0;
    for (int i = 1; i <= n; i++)
    {

        if (!st[i])
        {
            dfs(i);
            cur++;
        }
    }
    if (f)
    {
        cout << n - cur - 1 << endl;
    }
    else
    {
        cout << n - cur + 1 << endl; // 恢复后将一对相邻元素逆序
    }
}

int main()
{
    int t;
    t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }

    return 0;
}