排序的同时求逆序数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e6 +5;
int arr[maxn];
int cnt = 0;
void merge_sort(int b, int e)
{
    if(b == e)return;
    int mid = (b + e) / 2;
    merge_sort(b, mid);
    merge_sort(mid + 1, e);
    for(int i = b; i <= mid; i ++){
        cnt+=lower_bound(arr + mid + 1, arr + e + 1, arr[i]) - (arr + mid + 1);
    }
    sort(arr + b, arr + e + 1);
}
int main()
{
    int n;

    while(~scanf("%d",&n)){
        cnt = 0;
        for(int i = 1; i <= n; i ++){
            scanf("%d",&arr[i]);
        }
        merge_sort(1,n);
        for(int i = 1; i <= n; i ++){
            printf("%d ",arr[i]);
        }
        printf("\n%d\n",cnt);
    }
}