牛客1018逆序数-归并排序

题目：1018-逆序数_2021秋季算法入门班第十一章习题：线段树、树状数组

归并排序思想：数据结构合集 - 归并排序(非递归与递归算法过程, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

int a[M], b[M]; // a[M]待排序数组 b[M]临时数组
void ms(int l, int r) // 归并排序 merge sort
{if (l >= r)return;int mid = (l + r) / 2;ms(l, mid), ms(mid + 1, r);int k = 0, x = l, y = mid + 1; // 用回溯，进行排序while (x <= mid && y <= r)//对两个片段进行合并{if (a[x] <= a[y])b[k++] = a[x++];elseb[k++] = a[y++]; }while (x <= mid)b[k++] = a[x++];while (y <= r)b[k++] = a[y++];// 上面的 k从0开始往b[i]记录，所以这里的 j也是从0开始for (int i = l, j = 0; i <= r; i++, j++)a[i] = b[j];
}

逆序数题目的代码只要加一个计算即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, op;
const int M = 1e5 + 10;
int a[M], b[M]; // a[M] 待排序数组 b[M]临时数组
int ans;
void ms(int l, int r) // 归并排序 merge sort
{if (l >= r)return;int mid = (l + r) / 2;ms(l, mid), ms(mid + 1, r);int k = 0, x = l, y = mid + 1; // 用回溯，进行排序while (x <= mid && y <= r) // 对两个片段进行合并{if (a[x] <= a[y])b[k++] = a[x++];else // 此处说明a[x]>a[y],是逆序对,// 因为每个片段内都是升序的,所以有mid-x+1个数大于a[y]b[k++] = a[y++], ans += mid - x + 1;}while (x <= mid)b[k++] = a[x++];while (y <= r)b[k++] = a[y++];// 上面的 k从0开始往b[i]记录，所以这里的 j也是从0开始for (int i = l, j = 0; i <= r; i++, j++)a[i] = b[j];
}
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];ms(1, n);cout << ans;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;// cin >> t;while (t--){solve();}
}