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);// 读取原数组afor (i = 1; i <= n; ++i) scanf("%d", &a[i]);// 调用solve函数计算逆序对数ans = solve(1, n);// 输出逆序对的总数printf("%lld\n", ans);return 0; }