Inverse pair

Inverse pair

Charles Lv7
  2023-01-11 18:56:14 2023-01-11 18:56:14 Created   2023-07-30 10:52:49 2023-07-30 10:52:49 Updated      2.6k Words  11 Mins  

Inverse pair

逆序对

定义

设 A 为一个有 n 个数字的有序集 (n>1)，其中所有数字各不相同。
如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对，也称作逆序数。

对于一个包含N个非负整数的数组A[1…n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。
例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。

逆序对的计算

有序集中的逆序对数目是按照组合来计算的，对于大小为n的有序集，那么有$\frac{n(n+1)}{2} $种组合。

1. 朴素算法

枚举数组元素的所有组合，对于大小为n的数组，那么有$\frac{n(n+1)}{2} $种组合。

1
2
3
4
5
6
7
8
9
10
int countInversions(int a[], int length){
	int count = 0;
	for (int i = 0; i < length - 1; i++) {
		for (int j = i + 1; j < length; j++) {
			if (a[i] > a[j])
				count++;
		}
	}
	return count;
}

2. 借助冒泡排序

​ 冒泡排序的每一次交换就会消除一个逆序对, 交换一个相邻的逆序对，不会影响到其它的逆序对，所以可以计算冒泡排序在排序过程一共进行了多少次交换，由此得出数组的逆序对数。最普通的冒泡排序和枚举的循环次数一样多。但是枚举的过程没有元素交换，会比使用冒泡排序计算逆序对数快很多。

  • 借助冒泡排序只需要在交换两个元素的同时逆序对计数加1即可。普通的冒泡算法会试遍所有的组合，而改进的冒泡算法则可以减少这些检查，逆序对数少时就比枚举法快很多，但是逆序对数多的话就不行，因为排序有很大一部分时间花在元素交换上。
  • 缺点是计算的过程会消除逆序对，计算完成后，逆序对也被消除了，如果想保留数列，则需要复制数组，使用副本计算。

时间复杂度为$O(n^2)$

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
int countInversions_bubbleSort(int a[], int length){
    int count = 0;
    int left = 0, right = length - 1;	//遍历的范围
    int leftBound, rightBound;			//记录乱序的边界
    while (left < right) {
        leftBound = right, rightBound = left;
        for (int i = left; i < right; i++) {
            if (a[i] > a[i + 1]) {
                count++;
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                rightBound = i;				//修改右边界
            }
        }
        right = rightBound;			//修改范围
        for (int i = right; i > left; i--) {
            if (a[i - 1] > a[i]) {
                count++;
                int temp = a[i - 1];
                a[i - 1] = a[i];
                a[i] = temp;
                leftBound = i;				//修改左边界
            }
        }
        left = leftBound;			//修改范围
    }
    return count;
}

3. 借助插入排序

​ 插入排序的每一次元素移动可以看做相邻元素互换， 移动一次就消除一个逆序。
​ 所以可以用插入排序计算逆序对数，并且比用冒泡排序快。

时间复杂度为$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int countInversions_insertionSort(int a[], int length){
	int count = 0;
	for (int i = 1; i < length; i++) {
		int key = a[i];
		int j;
		for (j = i - 1; (j >= 0) && (a[j] > key); j--) {
			a[j + 1] = a[j];
			count++;
		}
		a[j + 1] = key;
	}
	return count;
}

4. 借助归并排序

一个升序数组，逆序对为0。数组中一个连续段之间的逆序对交换，只会影响段内的逆序对数，而不会影响段外的逆序对，段外的元素与段内的元素之间的逆序对数也不受影响
  将一个数组A从中间分成左右两部分， 分别是 $A [ l e f t ]$ . . . $A [ m i d ]$ 和 $A [ m i d + 1 ] $. . . $A [ r i g h t ]$。
  假设两部分分别有序，在归并过程中，i， j 分别表示左右两部分归并到的元素下标, 必有i < j。如果有A[i] > A[j]， 那么左边A[i]之后的元素也都会大于A[j], 所以A[j] 与 A[i] 到A[mid]的逆序对为$m i d − i + 1$ 。
  归并排序的两个有序数列归并，这两个有序数列在数组中是相邻的，所以交换这两个数列的元素，只会影响这两个数列元素之间的逆序对数。
  由此修改归并排序来计算逆序对， 逆序对在归并时计算。为了简便，就使用最普通的递归归并排序来说明。

  • 下面的临时数组是全局变量，是为了方便。如果想要把整个计算过程封装到函数内，可以参考递归归并排序的避免频繁开辟内存写法。

时间复杂度为$O ( n log ⁡ n )$

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
int a[LEN], temp[LEN];
//合并有序数列，并在合并时计算逆序对
int mergeCountInversions(int a[], int left, int mid, int right){
	int count = 0;
	//归并到临时数组中
	int i = left, j = mid + 1;
	for (int k = left; k <= right; k++) {
		if ((j > right) || (i <= mid) && (a[i] <= a[j]))
			temp[k] = a[i++];
		else {
			temp[k] = a[j++];
			count += mid - i + 1;		//计算逆序对数
		}
	}
	//拷贝回数组a
	for (int i = left; i <= right; i++)
		a[i] = temp[i];
	return count;
}
//通过归并排序计算逆序对
int countInversions_mergeSort(int a[], int left, int right){
	if (left < right) {
		int mid = left + (right - left) / 2;
		//当前数组内的逆序对数等于两个子数组的逆序对数加上归并时计算出的逆序对数
		return countInversions_mergeSort(a, left, mid) 
			+ countInversions_mergeSort(a, mid + 1, right)
			+ mergeCountInversions(a, left, mid, right);
	}
	else
		return 0;
}

5. 借助树状数组

树状数组C, C[x] 中保存等于x的元素的个数，初始值都为0。
  倒序扫描数列A， 每扫描到一个元素x，就在树状数组C[x]上加1，表示扫描到的x元素个数加1。然后在树状数组中查询前缀和S(x-1), 这个前缀和表示小于目前已经扫描到的元素中，比元素X小的有多少个，因为是从后面开始扫描的，所以先扫描的元素位置比元素x的位置靠后，又比元素x小，就是逆序了。树状数组的前缀和就是与元素X构成逆序的元素个数。

时间复杂度为$O ( n log ⁡ n )$

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
36
37
ll a[M], b[M], c[M], n, m;//b[]为逆序对数组，a[]为辅助数组
//树状数组模板
ll lowbit(ll x) {
    return x & (-x);
}
ll getsum(ll x) {
    ll i, ans = 0;
    for (i = x; i > 0; i -= lowbit(i)) {
        ans += c[i];
    }
    return ans;
}
void update(ll x, ll val) {
    while (x <= n) {
        c[x] += val;
        x += lowbit(x);
    }
}
//排序及逆序对处理
bool cmp(ll num1, ll num2) {
    if(b[num1] == b[num2]){
        return num1 > num2;
    }
    return b[num1] > b[num2];
}
ll lowbit_inverse_pair(ll b[], int length) {
    ll cnt = 0;
    for (int i = 1; i <= length; i++) {
        a[i] = i;
    }
    sort(a + 1, a + 1 + length, cmp);
    for (int i = 1; i <= n; i++) {
        update(a[i], 1);
        cnt += getsum(a[i] - 1);
    }
    return cnt;
}

模板题

火柴排队

[NOIP2013 提高组] 火柴排队

题目描述

涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$ \sum (a_i-b_i)^2$

其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $10^8-3$ 取模的结果。

输入格式

共三行，第一行包含一个整数 $n$，表示每盒中火柴的数目。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

一个整数，表示最少交换次数对 $10^8-3$ 取模的结果。

样例 #1

样例输入 #1

1
2
3
4
2 3 1 4
3 2 1 4
样例输出 #1
1
1

样例 #2

样例输入 #2
1
2
3
4
1 3 4 2
1 7 2 4
样例输出 #2
1
2

提示

【输入输出样例说明一】

最小距离是$ 0$，最少需要交换 $1$ 次，比如：交换第 $1 $列的前$ 2$ 根火柴或者交换第 $2$ 列的前 $2 $根火柴。

【输入输出样例说明二】

最小距离是 $10$，最少需要交换 $2$ 次，比如：交换第 $1$ 列的中间 $2$ 根火柴的位置，再交换第 $2$ 列中后 $2$ 根火柴的位置。

【数据范围】

对于 $10%$ 的数据， $1 \leq n \leq 10$；

对于 $30%$ 的数据，$1 \leq n \leq 100$；

对于 $60%$ 的数据，$1 \leq n \leq 10^3$；

对于 $100%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq$ 火柴高度 $< 2^{31}$。

AC代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define mod 99999997
#define ll long long
#define db double
#define pii pair<int, int>
typedef struct node {
    int val;
    int id;
} Node;
Node a[M], b[M];
int n, res[M], p[M], ans;
bool cmp(Node a, Node b) {
    return a.val < b.val;
}
void calc(int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    calc(l, mid);
    calc(mid + 1, r);
    int i = l, k = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (res[i] <= res[j]) {
            p[k++] = res[i++];
        } else {
            p[k++] = res[j++];
            ans += mid - i + 1;
            ans %= mod;
        }
    }
    while (i <= mid)
        p[k++] = res[i++];
    while (j <= r)
        p[k++] = res[j++];
    for (int i = l; i <= r; i++)
        res[i] = p[i];
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].val;
        a[i].id = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i].val;
        b[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        res[b[i].id] = a[i].id;
    }
    calc(1, n);
    cout << ans;
    return 0;
}
  • Title: Inverse pair
  • Author: Charles
  • Created at : 2023-01-11 18:56:14
  • Updated at : 2023-07-30 10:52:49
  • Link: https://charles2530.github.io/2023/01/11/inverse-pair/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
Swift-note-1 Swift-note-1 compiler-theory-1 compiler-theory-1 Cpp_note_1 Cpp_note_1
recommend_articles
Swift-note-1 Swift-note-1 compiler-theory-1 compiler-theory-1
Comments
On this page
Inverse pair
  1. Inverse pair
    1. 逆序对
      1. 定义
      2. 逆序对的计算
        1. 1. 朴素算法
        2. 2. 借助冒泡排序
        3. 3. 借助插入排序
        4. 4. 借助归并排序
        5. 5. 借助树状数组
    2. 模板题
      1. 输入格式
      2. 输出格式
      3. 样例 #1
        1. 样例输出 #1
      4. 样例 #2
        1. 样例输入 #2
        2. 样例输出 #2
      5. 提示
    3. AC代码