目录逆序对简介逆序对能做什么一些逆序对杂题总结逆序对简介逆序对定义给定一个序列\(a\)存在有序对\((i,j)\)满足\(ij\)且\(a_i a_j\)则称\((i,j)\)为一个逆序对。如何求序列逆序对对数根据定义对于一个下标\(i\)它能产生的所有逆序对\((i,j)\)即为区间\([i1,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 i1 ; 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; vectorint 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; mapint,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*21]; } void add(int pos, int l, int r, int aim) { if (l aim r aim) { tr[pos] 1; return; } int mid (lr) 1; if (aim mid) add(pos*2,l,mid,aim); else add(pos*21,mid1,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 (lr) 1; int sum 0; if (ql mid) sum query(pos*2,l,mid,ql,qr); if (qr mid) sum query(pos*21,mid1,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(a11,a1n1); sort(b11,b1n1); 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_{i2}\)以及\(a_{i1},a_{i3}\)。求任意次操作后可达的字典序最小的排列。注意到奇数位置只会和奇数位置交换偶数位置只会和偶数位置交换。这启示我们分奇偶来看。手玩样例发现除了\(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(vectorint a) { vectorint s(n10); 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; vectorint a(n10); vectorvectorint 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, vectorint tr) { tr[pos] tr[pos*2] tr[pos*21]; } void update(int pos, int l, int r, int k, vectorint tr) { if (l k r k) { tr[pos]; return; } int mid (lr) 1; if (k mid) update(pos*2,l,mid,k,tr); else update(pos*21,mid1,r,k,tr); push_up(pos,tr); } long long query(int pos, int l, int r, int ql, int qr, vectorint tr) { if (ql l qr r) return tr[pos]; int mid (lr) 1; long long sum 0; if (ql mid) sum query(pos*2,l,mid,ql,qr,tr); if (qr mid) sum query(pos*21,mid1,r,ql,qr,tr); return sum; } int n; void solve() { vectorvectorint a(n10,vectorint(n10)); vectorvectorint b(n10,vectorint(n10)); 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; } vectorint c(n*n10),d(n*n10); 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; vectorint tr1(4*N10),tr2(4*N10); 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题 类似奇数码问题(官方视频题解)总结涉及到元素交换、元素移动、区间循环左/右移、区间翻转的题目都可以往逆序对方向考虑。逆序对比起反映序列性质我觉得更像反映了某些操作的性质。