关于逆序对

逆序对一般可以用归并排序来做

一般的求逆序对如下：

给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 $i$ 个和第 $j$ 个元素，如果满足 $i<j$ 且 $a[i]>a[j]$，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 $n$，表示数列的长度。
第二行包含 $n$ 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
$1≤n≤100000$
数列中的元素的取值范围 $[1,10^9]$

样例

输入:
6
2 3 4 5 6 1

输出：
5

分析
在归并排序合并的过程中，不管是在a[i] <= a[j]中统计，还是在a[i] > a[i]中统计，由于它们是对称的两个部分，因此最终统计结果都是一样的。
需要注意的是，在a[i] <= a[j]中统计时，之后在while(i <= mid)中也需要统计；而在a[i] > a[j]中统计时，不需要在while(j <= r)中统计，因为j位于右半段，本来就应该更大，此时没有构成逆序。

AC代码
写法一

#include <iostream>
using namespace std;

typedef long long LL;

int n;
const int N = 100010;
int q[N];
int tmp[N];

LL merge_sort(int q[], int l, int r){
    if(l >= r) return 0;
    LL res = 0;
    int m = (l + r) >> 1;
    res =  merge_sort(q, l, m) + merge_sort(q, m + 1, r);
    int k = 0, i = l, j = m + 1;
    while(i <= m && j <= r){
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else{    //对这两个子序列
            tmp[k++] = q[j++];
            res += m - i + 1;   //关键
        }
    }
    while(i <= m) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}


int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    LL res = merge_sort(q, 0, n - 1);
    cout << res << endl;
    return 0;
}

写法二

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;
int a[N], tmp[N];
int n;
LL ans;

void merge_sort(int l, int r){
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
    //在a[i] <= a[j]这里统计，两部分是对称的，所以不管计算那个部分都是一样的。
    /*只不过如果统计的是a[i] <= a[j], 那么在之后i <= mid中也要统计，而如果统计的是a[i] > a[j],
      那么就不用在while(j <= r)中统计，因为j位于右半段，本身就应该比左半段大，没有形成逆序。*/
        if(a[i] <= a[j]){  
            ans += j - 1 - mid;
            tmp[k++] = a[i++];
        }
        else{
            tmp[k++] = a[j++];
        }
    }
    while(i <= mid){
        ans += r - mid;
        tmp[k++] = a[i++];
    }
    while(j <= r) tmp[k++] = a[j++];
    for(int i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    merge_sort(0, n - 1);
    printf("%lld\n", ans);

    return 0;
} 

扩展题

样例

输入：
3
3 2 1

输出：
9

解释
首先交换身高为 $3$ 和 $2$ 的小朋友，再交换身高为 $3$ 和 $1$ 的小朋友，再交换身高为 $2$ 和 $1$ 的小朋友，每个小朋友的不高兴程度都是 $3$，总和为 $9$。

分析
本题可以用树状数组或者归并排序来做，由于这篇文章是讨论逆序对，因此就用归并排序啦~

本题和传统求逆序对的不同在于每次只能交换相邻的两个数，且每个小朋友的不高兴值是一个等差数列。
因此求的不再是逆序的对数，而是构成每一对逆序的两个小朋友各自移动的距离。因此我们在合并的过程中，需要以每个小朋友为主角，去计算他自己需要新增多少移动距离。最终计算不高兴值的时候根据这个移动距离，用等差数列求和计算一下即可。

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
typedef long long LL;
typedef pair<int, int> PII;
const int N = 100010;
PII h[N], tmp[N];  //{身高，编号}
LL cnt[N]; 
int n;
LL ans;

void merge_sort(int l, int r){
	if(l >= r) return;
	int mid = l + r >> 1;
	merge_sort(l, mid), merge_sort(mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while(i <= mid && j <= r){
		if(h[i] <= h[j]){
			cnt[h[i].y] += j - mid - 1;  //j前面的数都比h[i].x小 
			tmp[k++] = h[i++];
		}
		else{
			cnt[h[j].y] += mid - i + 1;  //i后面的数都比h[j].x大 
			tmp[k++] = h[j++];
		}
	}
	while(i <= mid){
        cnt[h[i].y] += r - mid;
		tmp[k++] = h[i++]; 
	}
	
	while(j <= r) tmp[k++] = h[j++];
	
	for(int i = l, j = 0; i <= r; i++, j++) h[i] = tmp[j];
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%d", &h[i].x);
		h[i].y = i;
	}

	merge_sort(0, n - 1);
	for(int i = 0; i < n; i++){
		ans += (1 + cnt[i]) * cnt[i] / 2;
	}
	printf("%lld\n", ans);
	
	return 0;
}