前言

线性代数中对于一段数字序列的排列情况有这样一个定义:在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。也就是说,对于n个不同的元素,先规定各元素之间有一个标准次序(例如n个 不同的自然数,可规定从小到大为标准次序),于是在这n个元素的任一排列中,当某两个元素的先后次序与标准次序不同时,就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。(摘自 百度百科)

对于逆序数通俗的理解:对于序列中每个位置的的数,其之前比他的值大的个数之和,或者在其之后比他的值小的个数之和,如此称为逆序数


实现

实现手段:线段树、树状数组、离散化、归并排序、枚举

  • 我们容易根据逆序数的理解写出O(n^2)的模拟算法,是一个普通冒泡排序类似物:
int ans = 0;  //逆序数个数
int num[maxn];
for (int i = 1; i < n; i++) {
	for (int j = n - i; j > 0; j--) {
		if (num[j + 1] < num[j]) {
			swap(num[j + 1], num[j]);
			ans++;	
		}
	}
}
  • 如果当一段数字集中在某个范围中,还可以利用hash的特性,复杂度O(n*num(max)),但这个仍然是个暴力算法:
#include <iostream>
using namespace std;
int  a[100005];//存储有多少比它大的数字在它之前
int main()
{
    int n, m, i, j, k;
    cin >> n;
    long long int sum = 0;
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &m);
        sum = sum + a[m];// 有多少比它大的数字在他之前,就要加上多少组
        for (j = 0; j<m; j++)//在它之前的数字都+1
        {
            a[j]++;
        }
    }
    cout << sum << endl;
}
  • 上面那步的思想其实就是每次将数字压入数据集时,查询比当前数字排名来得大得数字数量,这个数字就是当前下标数字得逆序数。但是这个写法不足地方有两点:1,数据分散时空间复杂度高;2,每次都要执行一个O(num)大小的前缀操作。我们这是就可以利用线段树,树状数组的树形结构将前缀操作以及查询操作都均摊到O(logn)级别,从而提高效率。
细节

关于sum的含义是求得1~idx下标得前缀和,在这里根据方法2得思路就是rank <= idx的前缀数量,这里就要利用到一点容斥的思想:我们的目标是考虑当前有多少个比当前数排名大的数,当前全集为i,rank <= idx的数量为sum(idx),则当前 rank > idx 的数量为i-sum(idx)。其实c维护的就是rank的数量。举例:{7,4,3,8,6}

目前数据集 目前下标得到的逆序数 说明
{ } 初始化 逆序数为0,数据集为空
{7} 0 加入7,排名为4,逆序数为0,前面没有排名比他高的数字
{7,4} 1 加入4,排名为2,逆序数为1,前面排名有1个比他高的数字,分别为7
{7,4,3} 2 加入3,排名为1,逆序数为2,前面排名有2个比他高的数字,分别为7,4
{7,4,3,8} 0 加入8,排名为5,逆序数为0,前面排名有0个比他高的数字
{7,4,3,8,6} 2 加入6,排名为3,逆序数为2,前面排名有2个比他高的数字,分别为7,8
观察C数组的变化

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,c[100010];
int lowbit(int x)
{
	return x&(-x);
}
void add(int k,int num)
{
    while(k<=n)
    {
        c[k]+=num;
        k+=lowbit(k);
    }
}

int query(int k)
{
    int sum=0;
    while(k)
    {
        sum+=c[k];
        k-=lowbit(k);
    }
    return sum;
}
typedef struct nodee
{
    int x,i;
}node;
node maze[100010];
bool cmp(node u,node v)
{
	if(u.x==v.x)
		return u.i>v.i;
	return u.x<v.x;
}
int b[100010];

int main(void)
{
    int i,j,x,y;

    while(~scanf("%d",&n))
    {
        ll sum = 0;
        memset(c,0,sizeof(c));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&maze[i].x);
            maze[i].i = i;
        }
        sort(maze+1,maze+1+n,cmp);

        int cnt = 1;
        for(i=1;i<=n;i++){
            if(i!=1&&maze[i].x!=maze[i-1].x)
                cnt++;
            b[maze[i].i] = cnt;
        }

        for(i=1;i<=n;i++)
        {
            add(b[i],1);
            ll tmp = (i-query(b[i]));
            sum += tmp;
            cout << "\n逆序数 = " << tmp << " 排名 = " << b[i] << '\n';
            cout << "C数组:\n";
            for (int j = 1; j <= n; j++) {
							cout << c[j] << " ";
						}
        }
        printf("\n\n排列的逆序数为 = %lld\n",sum);
    }
    return 0;
}

  • 对于逆序数还有归并排序的求法,注意归并排序是稳定的排序算法,写法有细节要注意。
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = (int)1e5+5;
typedef long long ll;
typedef double db;
typedef long double ldb;

int val[maxn],tmp[maxn];
ll cnt;

void Merge (int l, int m, int r) {
	int i = l;
	int j = m + 1;
	int k = l;
	//归并排序为稳定排序,稳定的关键是mid后面那部分只有在小于前面的时候才往前提,相等不提!!!
	while (i <= m && j <= r) {
		if (val[i] > val[j]) {
			cnt += j-k; // 每当后段的数组元素提前时,记录提前的距离
			tmp[k++] = val[j++];
		}else {
			tmp[k++] = val[i++];
		}
	}
	
	while (i <= m) {
		tmp[k++] = val[i++];
	}
	while (j <= r) {
		tmp[k++] = val[j++];
	}
	for (int i = l; i <= r; i++) {
		val[i] = tmp[i];
	}
}

void MergeSort(int l, int r) {
	if (l < r) {
		int mid = l + ((r - l) >> 1);
		MergeSort(l, mid);
		MergeSort(mid + 1, r);
		Merge(l, mid, r);
	}
	return ;
}


int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> val[i];
	}
	cnt = 0;
	MergeSort(1, n);
	cout << cnt << '\n';
	return 0;
}



题目链接