47| 逆序对

一、核心思路这道题的核心是利用归并排序的分治思想在合并两个有序子数组的过程中统计逆序对数量时间复杂度为 O(nlogn)。1. 分治思想拆解分解将当前序列不断二分直到每个子数组只有 1 个元素天然有序。解决递归求解左右两个子数组内部的逆序对数量。合并合并两个有序子数组并统计跨左右子数组的逆序对即左半部分元素 右半部分元素且左元素下标 右元素下标。2. 合并阶段的逆序对统计假设左半部分为a[l..mid]已排序右半部分为a[mid1..r]已排序用双指针cur1遍历左半和cur2遍历右半若a[cur1] a[cur2]当前左半元素不会和右半元素形成逆序对直接将a[cur1]放入临时数组cur1。若a[cur1] a[cur2]左半部分从cur1到mid的所有元素都大于a[cur2]且下标都小于cur2因此新增mid - cur1 1个逆序对将a[cur2]放入临时数组cur2。合并完成后将临时数组的有序结果拷贝回原数组保证上层合并时子数组依然有序。二、代码实现#include bits/stdc.h using namespace std; #define int long long const int N 5e5 10; int a[N], tmp[N], n; int dfs(int l, int r) { if (l r) return 0; int ret 0; int mid (l r) 1; ret dfs(l, mid); ret dfs(mid 1, r); // 一左一右的情况 int cur1 l, cur2 mid 1; int i l; while(cur1 mid cur2 r) { if(a[cur1] a[cur2]) tmp[i] a[cur1]; else { ret mid - cur1 1; tmp[i] a[cur2]; } } while(cur1 mid) tmp[i] a[cur1]; while(cur2 r) tmp[i] a[cur2]; for(int j l; j r; j) a[j] tmp[j]; return ret; } signed main() { cin n; for (int i 1; i n; i) cin a[i]; cout dfs(1, n) endl; return 0; }