題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

ABC436E Minimum Swap

Problem Statement

題目簡述

給定一個長度為 $N$ 的排列 $P$ 。
目標是透過交換 $P$ 中任意兩個元素的操作，將其排序為 $(1, 2, \ldots, N)$ 。
令 $K$ 為將 $P$ 排序所需的最少交換次數。
請計算有多少對 $(i, j)$ ( $1 \le i < j \le N$ ) 滿足：若第一步交換 $P_i$ 與 $P_j$ ，則後續僅需 $K-1$ 次操作即可完成排序？

具體描述

換句話說，請問有多少組 $(i, j)$ 可以做為「最優交換」的第一步？

Constraints

約束條件

$2 \le N \le 3 \times 10^5$
$P$ 為長度 $N$ 的排列，且保證 $P \neq (1, \dots, N)$ 。

思路：置換環 (Cycle Decomposition)

這道題可以轉化為 置換環 (Cycle Decomposition) 的圖論問題。
我們可以將排列 $P$ 建構成一個有向圖，其中每個節點 $i$ 有一條有向邊指向 $P_i$ 。由於每個節點的出度與入度皆為 1，此圖必然由若干個不相交的環 (Disjoint Cycles) 構成。

根據置換群的性質，將一個排列排序所需的最小交換次數 $K$ 為：

K = N - C

其中 $N$ 是元素總數， $C$ 是環的總數（包含長度為 1 的自環）。

證明：為什麼

K = N - C

？

目標狀態：一個完全排序的序列 $(1, 2, \ldots, N)$ 等價於圖中有 $N$ 個自環，即 $C=N$ 。此時 $K = N - N = 0$ 。
操作影響：對於任意一次交換 $(i, j)$ $(i, j)$ ：
- 若 $i, j$ 在同一個環內（裂解）：該環會斷裂成兩個獨立的環。環的總數 $C$ 增加 1，距離目標 $N$ 更近一步（剩餘次數 $K-1$ ）。
- 若 $i, j$ 在不同的環內（合併）：這兩個環會合併成一個大環。環的總數 $C$ 減少 1，距離目標 $N$ 更遠一步（剩餘次數 $K+1$ ）。
結論：為了以最少次數 $N-C$ 達到目標，我們必須每次操作都讓環數 $+1$ （即每次都進行裂解）。

因此，題目要求「第一步操作後剩餘次數為 $K-1$ 」，等價於要求這一步操作必須是「裂解」操作。這意味著我們選取的 $(i, j)$ 必須位於同一個環中。

解題策略

我們只需要找出所有的環，計算每個環內有多少對不同節點 $(i, j)$ 即可。

演算法流程

建立一個 vis 陣列標記節點是否已訪問。
遍歷 $1$ $1$ 到 $N$ $N$ 的每個節點 $i$ $i$ ：
- 若 $i$ 尚未訪問，表示發現一個新的環。
- 沿著 $i \to P_i \to P_{P_i} \dots$ 遍歷該環，同時計算環的大小（節點數） $L$ ，並標記經過的節點為已訪問。
對於大小為 $L$ 的環，其內部的任兩點交換都是合法操作，故對答案的貢獻為 $\binom{L}{2} = \frac{L(L-1)}{2}$ 。
累加所有環的貢獻即為最終答案。

複雜度分析

時間複雜度： $\mathcal{O}(N)$ 。每個節點在尋找環的過程中只會被訪問一次。
空間複雜度： $\mathcal{O}(N)$ 。需要維護 vis 陣列來標記已訪問的節點，以及存儲輸入的排列 $P$ 。

Code

def solve():
    n = int(input())
    P = list(map(lambda x: int(x) - 1, input().split()))
    assert len(P) == n

    ans = 0
    vis = [False] * n
    for u in range(n):
        if vis[u]:
            continue
        cnt = 0
        while not vis[u]:
            vis[u] = True
            u = P[u]
            cnt += 1
        ans += cnt * (cnt - 1) // 2
    print(ans)

if __name__ == "__main__":
    solve()

寫在最後

PROMPT