【题目描述】
给定一个序列a1,a2,…,an
，如果存在i<j并且ai>aj
，那么我们称之为逆序对，求逆序对的数目。
【输入】
第一行为n
,表示序列长度，接下来的n行，第i+1行表示序列中的第i
个数。
【输出】
所有逆序对总数。
【输入样例】
4 3 2 3 2
【输出样例】
3
【提示】
N≤105，Ai≤105
。
#include<iostream>
using namespace std;
#define N 500005//数组长度
int a[N], t[N];
long long ct;//逆序数
void mergeSort(int l, int r)
{
if(l >= r)
return;
int mid = (l + r)/2;
mergeSort(l, mid);
mergeSort(mid+1, r);
int ti = l, li = l, ri = mid+1;//li第一个段数组中的下标 ri第二段数组中的下标 ti临时数组中的下标
while(li <= mid && ri <= r)
{
if(a[li] <= a[ri])
t[ti++] = a[li++];
else//如果a[ri] < a[li] 此时a[ri]与左侧数组剩余的mid-li+1个数字构成逆序对
{
ct += mid-li+1;
t[ti++] = a[ri++];
}
}
while(li <= mid)
t[ti++] = a[li++];
while(ri <= r)
t[ti++] = a[ri++];
for(int i = l; i <= r; ++i)
a[i] = t[i];
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
mergeSort(1, n);
cout << ct;
return 0;
}
