在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。
Input
第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）
Output
输出逆序数
Input示例
4
2
4
3
1
Output示例
4
树状数组的方法求逆序对
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 50005;
int bit[maxn];
int n, q;
struct node {
int i, x;
}arr[maxn];
map<int, int>mp;
int lowbit(int r) {
return r & (-r);
}
void add(int i, int x) {
while(i <= n) {
bit[i] += x;
i += lowbit(i);
}
}
int query(int i) {
int sum = 0;
while(i > 0) {
sum += bit[i];
i -= lowbit(i);
}
return sum;
}
bool cmp(node p, node q) {
return p.x < q.x;
}
/*void output() {
for(int i = 1; i <= n; i++)
cout << bit[i] << " ";
cout << endl;
}
*/
int main() {
cin >> n;
ll ans = 0;
memset(bit, 0, sizeof(bit));
for(int i = 1; i <= n; i++) {
cin >> arr[i].x;
arr[i].i = i;
}
sort(arr + 1, arr + n + 1, cmp);
for(int i = 1; i <= n; i++) {
mp.insert(make_pair(arr[i].i, i));
}
for(int i = 1; i <= n; i++) {
add(mp[i], 1);
//output();
ans += i - query(mp[i]);
}
cout << ans << endl;
return 0;
}归并排序的方法求逆序对
#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
int arr[50005], temp[50005];
void mergearray(int a[], int l, int mid, int r, int temp[]) {
int i = l, j = mid + 1;
int m = mid, n = r;
int k = 0;
while(i <= m && j <= n) {
if(a[i] <= a[j]) {
temp[k++] = a[i++];
}
else {
temp[k++] = a[j++];
ans += (m + 1) - i;
}
}
while(i <= m) {
temp[k++] = a[i++];
}
while(j <= n) {
temp[k++] = a[j++];
}
for(i = 0; i < k; i++) {
a[l++] = temp[i];
}
}
void mergesort(int a[], int l, int r, int temp[]) {
if(l < r) {
int mid = (l + r) >> 1;
mergesort(a, l, mid, temp);
mergesort(a, mid + 1, r, temp);
mergearray(a, l, mid, r, temp);
}
}
int main() {
cin >> n;
ans = 0;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
mergesort(arr, 0, n - 1, temp);
cout << ans << endl;
return 0;
}