目录
- 逆序对简介
- 逆序对能做什么
- 一些逆序对杂题
- 总结
逆序对简介
逆序对定义
给定一个序列\(a\)，存在有序对\((i,j)\)，满足\(i<j\)且\(a_i > a_j\)，则称\((i,j)\)为一个逆序对。
如何求序列逆序对对数
根据定义：对于一个下标\(i\)，它能产生的所有逆序对\((i,j)\)，即为区间\([i+1,n]\)中小于\(a_i\)的数的个数。
最朴素的\(O(n^2)\)做法如下：
/* by 01022.hk - online tools website : 01022.hk/zh/httpheader.html */ for (int i = 1 ; i <= n ; i++) { for (int j = i+1 ; j <= n ; j++) { if (a[j] < a[i]) cnt++; } }这个过程可以通过树状数组或线段树优化：从后往前依次插入\(a_i\)，并通过树状数组查询小于\(a_i\)的数的个数。当然，从前往后插入\(a_i\)，并查询大于\(a_i\)的数的个数同样可以。以上做法复杂度为\(O(nlogn)\)。
还有一种通过归并排序求逆序对的做法，这里不做赘述。
模版题 P1908 逆序对
本题需要离散化后再建树状数组。
以下采用的是从后往前插入的方法。
/* by 01022.hk - online tools website : 01022.hk/zh/httpheader.html */ #include <iostream> #include <algorithm> #include <vector> using namespace std; using ll = long long; const int N = 5e5 + 10; vector<int> vec; int a[N],tr[N]; int siz; int lowbit(int x) { return x & -x; } void insert(int x) { while (x <= siz) { tr[x]++; x += lowbit(x); } } ll query(int x) { ll sum = 0; while (x) { sum += tr[x]; x -= lowbit(x); } return sum; } int id(int x) { return lower_bound(vec.begin(),vec.end(),x) - vec.begin() + 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; vec.push_back(a[i]); } //离散化 sort(vec.begin(),vec.end()); auto e = unique(vec.begin(),vec.end()); vec.erase(e,vec.end()); siz = vec.size(); ll ans = 0; for (int i = n ; i >= 1 ; i--) { if (!a[i]) continue; ans += query(id(a[i])-1); insert(id(a[i])); } cout << ans << endl; return 0; }逆序对能做什么
1、逆序对数量 = 冒泡排序元素交换次数
这个结论也可以说是：通过相邻交换得到升序排序的最小操作数。
如何理解这个结论？直观感受：当冒泡排序进行到\([1,i-1]\)都已经排列有序时，此时要移动下标\(i\)位置的元素到对应位置。这个元素要交换的次数，就等于它左边比它大的元素个数。实际上，对下标\(i\)求前面比它大的元素个数，这就是在求逆序对。
举个例子：\(\{[1,3,4],2,5\}\)中，当对\(2\)进行冒泡排序时，数组会变为：\(\{[1,2,3,4],5\}\)，也就是和\(4、3\)依次交换。
从逆序对的角度讲，每一次相邻交换，都会使逆序对的数量减1。因此逆序对数量就等于元素交换次数。
裸题 P1116 车厢重组
这题数据比较水，甚至可以不用树状数组。
以下是树状数组从前往后插入的写法。
#include <iostream> #include <algorithm> #include <vector> using namespace std; using ll = long long; const int N = 1010; int a[N],tr[N]; int n; int lowbit(int x) { return x & -x; } void insert(int x) { while (x <= n) { tr[x]++; x += lowbit(x); } } ll query(int x) { ll sum = 0; while (x) { sum += tr[x]; x -= lowbit(x); } return sum; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; ll ans = 0; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; insert(a[i]); ans += query(n) - query(a[i]); } cout << ans << endl; return 0; }再看一道非常经典的题目
P1966 [NOIP 2013 提高组] 火柴排队
题意：有\(a、b\)两个数组，都支持数组内相邻元素交换，求 $ \sum (a_i-b_i)^2$ 最小化时，最少交换次数，答案对\(10^8-3\)取模。
本题难点在于如何最小化 $ \sum (a_i-b_i)^2$。这里直接说结论：将\(a\)和\(b\)数组分别排序后，对应位置的\(a_i\)和\(b_i\)在同一行时，该式最小。（该策略可以用微扰法证明，这不是本篇的重点，详细证明可参考洛谷题解区）
于是问题转化为：使\(a\)和\(b\)中排名相同的元素都处于同一行，需要的最少交换次数。
首先，当两个数组都可以交换时，一定可以只对一个数组进行操作。因为对\(a\)中的两个元素进行交换，和交换\(b\)中对应位置的元素是等价的。
类似求最长公共子序列的方法，我们固定数组\(b\)不动，将\(a_i\)应该移动到的位置映射出来，将\(a\)按映射值排序，就可以把问题转化成求升序排列的最小交换次数。
例如：\(a = [1,3,2,4],b = [4,3,2,1]\)
a原值 1 3 2 4 b原值 4 3 2 1 a映射 4 2 3 1线段树实现：
#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; const int MOD = 1e8 - 3; const int N = 1e5 + 10; map<int,int> mp1,mp2,mp3; int a[N],b[N]; int a1[N],b1[N]; int tr[4*N]; void push_up(int pos) { tr[pos] = tr[pos*2] + tr[pos*2+1]; } void add(int pos, int l, int r, int aim) { if (l == aim && r == aim) { tr[pos] = 1; return; } int mid = (l+r) >> 1; if (aim <= mid) add(pos*2,l,mid,aim); else add(pos*2+1,mid+1,r,aim); push_up(pos); } int query(int pos, int l, int r, int ql, int qr) { if (qr < ql) return 0; if (ql <= l && qr >= r) return tr[pos]; int mid = (l+r) >> 1; int sum = 0; if (ql <= mid) sum += query(pos*2,l,mid,ql,qr); if (qr > mid) sum += query(pos*2+1,mid+1,r,ql,qr); return sum; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; a1[i] = a[i]; } for (int i = 1 ; i <= n ; i++) { cin >> b[i]; b1[i] = b[i]; } sort(a1+1,a1+n+1); sort(b1+1,b1+n+1); for (int i = 1 ; i <= n ; i++) { mp1[a1[i]] = i; mp2[b1[i]] = i; } for (int i = 1 ; i <= n ; i++) { a[i] = mp1[a[i]]; b[i] = mp2[b[i]]; mp3[b[i]] = i; } for (int i = 1 ; i <= n ; i++) a[i] = mp3[a[i]]; int ans = 0; for (int i = n ; i >= 1 ; i--) { add(1,1,n,a[i]); ans += query(1,1,n,1,a[i]-1); ans %= MOD; } cout << ans << endl; return 0; }2、判断数组变化的可达性
这句话比较抽象。具体点就是：一个数组通过元素交换、区间翻转等操作后，能否得到另一个数组。
由于这些操作一般都伴随着逆序对的变化，所以可通过逆序对的数量变化、奇偶性变化等来判断是否可达。
CF2101B Quartet Swapping
题意：给定一个长度为\(n\)的排列。支持一种操作：选择一个下标\(1 \leq i \leq n-3\)，同时交换\(a_i , a_{i+2}\)以及\(a_{i+1},a_{i+3}\)。求任意次操作后，可达的字典序最小的排列。
注意到奇数位置只会和奇数位置交换，偶数位置只会和偶数位置交换。这启示我们分奇偶来看。手玩样例发现，除了\(a_{n-2}\)和\(a_n\)，其他位置可以构造出最优解。即：可能出现\(a_{n-2} > a_n\)。
这种涉及到元素交换的题目，都可以往逆序对方向想想。本题可以将奇数位置和偶数位置单独拿出来计算逆序对。
考虑一次操作会对逆序对产生什么影响。一对元素的交换必定导致逆序对的数量+1或-1，也就是奇偶性翻转。由于奇位置和偶位置各有一对元素交换，因此奇数位置的逆序对奇偶性和偶数位置的逆序对奇偶性同时变化。
字典序最小的排列中，奇数位置和偶数位置的逆序对均为0，因此，只有当奇偶位置逆序对奇偶性相同时，才可能构造出最优解，否则交换\(a_n\)和\(a_{n-2}\)。
#include <iostream> #include <algorithm> #include <vector> using namespace std; using ll = long long; int n; int lowbit(int x) { return x & -x; } ll count(vector<int> a) { vector<int> s(n+10); auto update = [&](int x) { while (x <= n) { s[x]++; x += lowbit(x); } }; auto query = [&](int x) { int t = 0; while (x) { t += s[x]; x -= lowbit(x); } return t; }; ll sum = 0; for (int i = a.size()-1 ; i >= 0 ; i--) { update(a[i]); sum += query(a[i]-1); } return sum; } void solve() { cin >> n; vector<int> a(n+10); vector<vector<int>> vec(2); ll cnt1 = 0, cnt2 = 0; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; vec[i%2].push_back(a[i]); } cnt1 = count(vec[0]); cnt2 = count(vec[1]); sort(vec[0].begin(),vec[0].end()); sort(vec[1].begin(),vec[1].end()); int p[2] = {0}; for (int i = 1 ; i <= n ; i++) a[i] = vec[i%2][p[i%2]++]; if (cnt1 % 2 != cnt2 % 2) swap(a[n],a[n-2]); for (int i = 1 ; i <= n ; i++) cout << a[i] << " "; cout << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; while (T--) solve(); return 0; }P10454 奇数码问题
题意：\(n \times n\)的矩阵中有\(1\)个空格和\(1 \sim n^2-1\)这几个数。空格可以进行上、下、左、右移动。问初始局面和最终局面是否是可达的。
一道非常邪门的题目。
将矩阵按行拆开，排列成一维数组(忽略这个空格位置)。手动模拟几轮后注意到：空格的左、右移动不会改变这个数组，逆序对奇偶性不变。而上、下移动相当于把一个元素在这个数组中移动了\(n-1\)位。由于\(n\)为奇数，因此逆序对奇偶性也不会发生改变。
因此仅当将初始局面和最终局面，拍扁成一维数组后逆序对奇偶性不变时，它们是互相可达的。
这题提供了一种思路：矩阵的某些操作，也可以通过一些方式转化为判断逆序对的性质。
#include <iostream> #include <unordered_map> #include <vector> using namespace std; void push_up(int pos, vector<int>& tr) { tr[pos] = tr[pos*2] + tr[pos*2+1]; } void update(int pos, int l, int r, int k, vector<int>& tr) { if (l == k && r == k) { tr[pos]++; return; } int mid = (l+r) >> 1; if (k <= mid) update(pos*2,l,mid,k,tr); else update(pos*2+1,mid+1,r,k,tr); push_up(pos,tr); } long long query(int pos, int l, int r, int ql, int qr, vector<int>& tr) { if (ql <= l && qr >= r) return tr[pos]; int mid = (l+r) >> 1; long long sum = 0; if (ql <= mid) sum += query(pos*2,l,mid,ql,qr,tr); if (qr > mid) sum += query(pos*2+1,mid+1,r,ql,qr,tr); return sum; } int n; void solve() { vector<vector<int>> a(n+10,vector<int>(n+10)); vector<vector<int>> b(n+10,vector<int>(n+10)); for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= n ; j++) { cin >> a[i][j]; // cout << a[i][j] << " "; } // cout << endl; } for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= n ; j++) { cin >> b[i][j]; // cout << b[i][j] << " "; } // cout << endl; } vector<int> c(n*n+10),d(n*n+10); int cnt1 = 0, cnt2 = 0; for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= n ; j++) { c[++cnt1] = a[i][j]; d[++cnt2] = b[i][j]; } } int N = n * n; vector<int> tr1(4*N+10),tr2(4*N+10); long long sum1 = 0, sum2 = 0; for (int i = N ; i >= 1 ; i--) { if (c[i] == 0) continue; update(1,1,N,c[i],tr1); if (c[i] != 1) sum1 += query(1,1,N,1,c[i]-1,tr1); } for (int i = N ; i >= 1 ; i--) { if (d[i] == 0) continue; update(1,1,N,d[i],tr2); if (d[i] != 1) sum2 += query(1,1,N,1,d[i]-1,tr2); } if ((sum1 % 2) == (sum2 % 2)) cout << "TAK" << endl; else cout << "NIE" << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while (cin >> n) solve(); return 0; }注意：通过逆序对性质判断可达性，一般要证明充要性。
以 Quartet Swapping 这题为例：只有当奇偶位置逆序对的奇偶性相同时，才可能构造出最优解，这个结论是很草率的，因为我们实际只能看出它的必要性，即：能构造出最优解时，奇偶位置独立算的逆序对的奇偶性一致。
这题的充分性证明比较困难（至少我不会），但有一种比较无脑的方法，就是归纳法。在小样例的情况下手动模拟，猜测充分性是否成立。
一些逆序对杂题
CF911D Inversion Counting 区间翻转对逆序对的影响
2024ICPC沈阳D题 通过奇偶做博弈分析
2025牛客多校第七场A题 类似奇数码问题(官方视频题解)
总结
涉及到元素交换、元素移动、区间循环左/右移、区间翻转的题目都可以往逆序对方向考虑。逆序对比起反映序列性质，我觉得更像反映了某些操作的性质。
