AcWing 788. 18行代码 逆序对
原题链接
简单
const int N = 1e5 + 5;
int num[N], tmp[N];
long long ans = 0;
void find(int left, int right) {
if (left >= right)return;
int mid = (left + right) >> 1,cnt=left;
find(left, mid), find(mid+1, right);
for (int t = left; t <= right; t++)tmp[t] = num[t];
tmp[right + 1] = 1<<30;
for (int l = left, r = mid+1; l <= mid;cnt++)
if (tmp[l] <= tmp[r])num[cnt] = tmp[l++], ans +=(long long) r - mid-1;
else num[cnt] = tmp[r++];
}
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++)scanf("%d", &num[i]);
find(1, n);
cout << ans;
}