[ARC167D] Good Permutation 题解

题意

对于一个长度为 \(N\) 的排列 \(Q\)，定义其为好的，当且仅当

• 对于任意整数 \(i \in \left[1, N\right]\)，在进行若干次操作 \(i \leftarrow Q_i\) 后可以得到 \(i = 1\)。

给定一个排列 \(P\)，定义一次操作为交换两个数。定义 \(M\) 为可以将 \(P\) 变为一个好的的排列的最小操作次数，求在操作 \(M\) 次的情况下可以得到的字典序最小的排列。

（\(1 \le N \le 2 \times 10^5\)）。

题解

转化为图论模型，考虑对于对于所有 \(i \in \left[1, N\right]\)，建边 \(i \rightarrow P_i\)，因为每个点的出度和入度均为 \(1\)，所以建出的图一定是若干个环。而一个好的排列最后建出的图就是一个长度为 \(N\) 的环。而每次操作实质上就是合并两个环。

由于所有节点最后均与 \(1\) 在统一个环中，并且我们要求字典序最小，那么我们可以从小到大去枚举一个元素 \(i\)，若其与 \(1\) 不在同一个环中就交换其所在环的一个元素与 \(1\) 所在环的一个元素，考虑到需要字典序最小，那么我们可以交换与 \(1\) 在同一个环的所有元素中第一个大于当前元素，若与 \(1\) 在同一个环的所有元素均小于当前元素，那么我们将其与最后一个位置交换。

若出现后者的情况，可以发现与 \(1\) 联通的集合为 \(\left\{1, 2, 3, \cdots, i - 1\right\}\)，由于值的集合和下标集合相同，所以这种情况下 \(i\) 会与 \(P_{i - 1}\) 交换。若出现前者的情况，由于其是一个环，那么一定存在边 \(u \rightarrow v\) 满足， \(u < i - 1, v > i\)，即存在 \(j \le i - 1, P_j > i\)。此时的 \(j\) 一定满足对于任意 \(k < j\)，有 \(P_k < i \Rightarrow P_k < i + 1\)，也就是说被 \(i\) 排除的位置集合也不可能进入 \(i + 1\) 的决策集合，换句话说，每次交换位置的位置是单调递增的。那么我们使用一个指针 \(j\) 去维护即可，若找到了 \(P_j > i\) 或扫描到了 \(i - 1\) 那么就执行交换操作。

总复杂度 \(\mathcal{O}(N)\)，可以通过本题。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bool> bitset;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType T;

    std::cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        valueType N;

        std::cin >> N;

        ValueVector P(N + 1), pos(N + 1);

        for (valueType i = 1; i <= N; ++i) {
            std::cin >> P[i];

            pos[P[i]] = i;
        }

        valueType pointer = 1;

        bitset visited(N + 1, false);

        {
            valueType y = pos[1];

            while (!visited[P[y]]) {
                visited[P[y]] = true;

                y = P[y];
            }
        }

        for (valueType i = 1; i <= N; ++i) {
            if (visited[i])
                continue;

            valueType const x = pos[i];

            while (pointer < i - 1)
                if (P[pointer] < i)
                    ++pointer;
                else
                    break;

            {
                valueType y = x;

                while (!visited[P[y]]) {
                    visited[P[y]] = true;

                    y = P[y];
                }
            }
            std::swap(P[x], P[pointer]);
        }

        std::copy(P.begin() + 1, P.end(), std::ostream_iterator<valueType>(std::cout, " "));

        std::cout << std::endl;
    }

    std::cout << std::flush;

    return 0;
}