当前位置：首页 > news >正文

浅谈逆序对在算法竞赛中的具体运用

news 2026/3/26 19:40:03

逆序对简介

逆序对定义

给定一个序列 $a$，存在有序对 $(i,j)$，满足 $i<j$ 且 $a_i > a_j$，则称 $(i,j)$ 为一个逆序对。

如何求序列逆序对对数

根据定义：对于一个下标 $i$，它能产生的所有逆序对 $(i,j)$，即为区间 $[i+1,n]$ 中小于 $a_i$ 的数的个数。

最朴素的 $O(n^2)$ 做法如下：

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 逆序对
本题需要离散化后再建树状数组。
以下采用的是从后往前插入的方法。

#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 这题为例：只有当奇偶位置逆序对的奇偶性相同时，才可能构造出最优解，这个结论是很草率的，因为我们实际只能看出它的必要性，即：能构造出最优解时，奇偶位置独立算的逆序对的奇偶性一致。

这题的充分性证明比较困难（至少我不会），但有一种比较无脑的方法，就是归纳法。在小样例的情况下手动模拟，猜测充分性是否成立。