23 1，这个1要插入到23前面之前，说明，23比1大。所在d1-d2+1个统计进来。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 500005 using namespace std; int a[N], b[N], c[N]; // a是原数组，b是左半边数组，c是右半边数组 // merge函数用于合并左右子数组，并计算逆序对个数 long long merge(int l, int r, int mid) { int i, b1 = 0, c1 = 0, b2 = 1, c2 = 1; // 将左半边数组从a[l]到a[mid]复制到b数组 for(i = 1; i <= mid; ++i) b[++b1] = a[i]; // 左半边 b1成为b的长度 // 将右半边数组从a[mid+1]到a[r]复制到c数组 for(i = mid + 1; i <= r; ++i) c[++c1] = a[i]; // 右半边 c1成为c的长度 long long ans = 0; // 用来记录逆序对的个数 // 对[l, r]区间内的所有元素进行归并排序 for(i = l; i <= r; ++i) { if(b1 >= b2 && (c1 + 1 == c2 || b[b2] <= c[c2])) { // 如果左半边的元素还有剩余，且左半边的当前元素小于等于右半边的当前元素 a[i] = b[b2++]; // 将左半边的元素放入原数组 } else { // 否则，选择右半边的元素 a[i] = c[c2++]; // 将右半边的元素放入原数组 // 计算逆序对数：左半边剩余的元素均大于当前右半边的元素 ans += b1 - b2 + 1; // 说明左半边b数组中的所有剩余元素都大于c[c2]，因此都形成了逆序对 } } return ans; // 返回当前区间[l, r]的逆序对数 } // solve函数用于分治地计算逆序对数 long long solve(int l, int r) { // 参数l, r表示区间a[l] ~ a[r] // 返回值为区间[l, r]内的逆序对个数 if (l == r) return 0; // 如果区间只有一个元素，则没有逆序对 int mid = (l + r) >> 1; // 计算区间的中点 long long ans = 0; ans += solve(l, mid); // 递归计算左半边的逆序对 ans += solve(mid + 1, r); // 递归计算右半边的逆序对 ans += merge(l, r, mid); // 合并两个子区间并计算跨区间的逆序对 return ans; // 返回[l, r]区间的总逆序对数 } int main() { int n, i; long long ans; // 读取数组的大小 scanf("%d", &n); // 读取原数组a for (i = 1; i <= n; ++i) scanf("%d", &a[i]); // 调用solve函数计算逆序对数 ans = solve(1, n); // 输出逆序对的总数 printf("%lld\n", ans); return 0; }