目录
一、前置基础：置换与置换环的核心概念
1. 置换环的定义与分解
循环分为两类：
2. 最小交换次数 K 的计算（核心公式）
（1）单个循环的最小交换次数
（2）整个排列的最小交换次数 K
二、交换操作对置换环与 K 的影响
（1）对循环结构的影响
（2）对 K 的影响
（1）对循环结构的影响
（2）对 K 的影响
三、题目核心：合法首次操作的判定与计数
四、代码
E - Minimum Swaphttps://atcoder.jp/contests/abc436/tasks/abc436_e
本文将置换环的核心理论与题目要求深度结合，从原理推导到题目解法形成完整逻辑链，涵盖置换环的分解、最小交换次数的计算、交换操作对循环的影响，以及最终题目答案的推导。
一、前置基础：置换与置换环的核心概念
对于一个长度为 N 的排列 P（P 是 1,2,…,N 的一个排列，即每个数恰好出现一次），置换环是描述排列无序性的核心工具。
1. 置换环的定义与分解
排列的本质是位置到值的映射关系：对于位置 i，P [i] 表示该位置上的数值。从任意位置 i 出发，沿着 i → P [i] → P [P [i]] → … 的路径遍历，直到回到起始位置 i，这条闭合路径就构成一个置换环（简称循环）。
循环分为两类：
自环：若 P [i] = i，则 i 自身构成一个长度为 1 的循环（元素已在正确位置，无操作意义）。
非自环：若 P [i] ≠ i，则遍历路径形成长度≥2 的循环（元素需要交换才能归位）。
示例：
排列 P = [3,1,4,2,5]（位置 1~5）：循环 1：1 → 3 → 4 → 2 → 1（长度 4，非自环）；
循环 2：5 → 5（长度 1，自环）。
排列 P = [2,1,4,3]（位置 1~4）：循环 1：1 → 2 → 1（长度 2，非自环）；
循环 2：3 → 4 → 3（长度 2，非自环）。
2. 最小交换次数 K 的计算（核心公式）
将排列还原为有序序列 (1,2,…,N) 的最小交换次数，由置换环的结构决定：
（1）单个循环的最小交换次数
对于一个长度为 len 的非自环循环，要将其所有元素还原到正确位置，需要 len - 1 次交换。
原理：每一次交换最多能让循环的长度缩短 1，最终剩余 1 个元素时无需交换，因此总次数为 len - 1。
示例：长度 2 的循环需 1 次交换，长度 4 的循环需 3 次交换。
（2）整个排列的最小交换次数 K
设排列分解后有：
m 个非自环循环（长度分别为 len₁, len₂, …, lenₘ）；
S = sum (lenᵢ)：所有非自环元素的总数（即所有长度≥2 的循环的长度之和）。
则整个排列的最小交换次数为：
K = Σ（从 i=1 到 m）(len_i - 1) = S - m
这是后续分析的核心公式，建立了置换环与最小交换次数的直接关联。
示例验证：
排列 [3,1,4,2,5]：S=4，m=1，则 K=4-1=3；
排列 [2,1,4,3]：S=4，m=2，则 K=4-2=2。
二、交换操作对置换环与 K 的影响
题目中允许的操作是：选择任意 i<j，交换 P [i] 和 P [j]。不同位置的交换会对置换环的结构产生不同影响，进而改变最小交换次数 K。
1. 情况 1：交换同一非自环循环内的元素
（1）对循环结构的影响
原循环（长度 len）会拆分为两个新的循环（长度为 a 和 b，满足 a + b = len）。
原理：交换环内两个点的映射关系，相当于在环上 “切两刀”，将一个闭合环拆分为两个独立的小环，总长度保持不变。
示例：循环 1→3→4→2→1（长度 4），交换位置 2 和 3 的元素后，拆分为 1→3→1（长度 2）和 2→4→2（长度 2）。
（2）对 K 的影响
非自环元素总数 S：不变（仅循环拆分，元素数量无增减）；
非自环循环数量 m：增加 1（一个变两个，m' = m + 1）；
新的最小交换次数 K'：
K' = S - m' = S - (m + 1) = K - 1
结论：交换同一循环内的元素，会让最小交换次数减少 1。
2. 情况 2：交换不同非自环循环内的元素
（1）对循环结构的影响
两个原循环（长度 len₁和 len₂）会合并为一个新的循环（长度 len = len₁ + len₂）。
原理：交换两个独立环的元素，相当于用这两个元素作为 “桥梁”，将两个环连接成一个更大的闭合环，总长度为原两环长度之和。
示例：循环 1→2→1（长度 2）和 3→4→3（长度 2），交换位置 1 和 3 的元素后，合并为 1→4→3→2→1（长度 4）。
（2）对 K 的影响
非自环元素总数 S：不变（仅循环合并，元素数量无增减）；
非自环循环数量 m：减少 1（两个变一个，m' = m - 1）；
新的最小交换次数 K'：
K' = S - m' = S - (m - 1) = K + 1
结论：交换不同循环内的元素，会让最小交换次数增加 1。
三、题目核心：合法首次操作的判定与计数
1. 题目要求回顾
设 K 为将 P 还原为有序的最小交换次数；需统计合法的首次操作数：选择 (i,j) 作为首次操作后，能通过后续操作让总操作次数恰好为 K（最小次数）。
2. 合法首次操作的约束条件
首次操作用了 1 次，设后续还原所需的最小交换次数为 K'，则总操作次数为 1 + K'。要让总次数恰好为 K，必须满足：1 + K' = K → K' = K - 1即：合法的首次操作必须让交换后的最小交换次数 K' = K - 1。
所以只能在同一循环内交换
四、代码
#include <bits/stdc++.h> using namespace std; #define int long long // priority_queue<int, vector<int>, greater<int> > q; const int N = 4e5+10; const int inf=1e9; int p[N]; void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i]; } bool st[n+1]={false}; long long ans = 0; for (int i = 1; i <= n; i++) { if (!st[i]) { int c = i; int len = 0; while (!st[c]) { st[c] = 1; c = p[c]; len++; } ans += len * (len - 1) / 2; } } cout << ans << endl; } signed main() { int q=1; // cin >> q; while (q--) { solve(); } return 0; }
