逆序对的数量—归并排序和树状数组

逆序对就是数组中的两个数，下标小的那个数的值大于下标大的那个数。

这就是一组逆序对。

5 4 3 2 1

像这组数据，一共有4 + 3 + 2 + 1个逆序对。

主要有两种求解方式，归并排序和树状数组。

归并排序

众所周知，归并排序是通过将一个数组分为两部分，分别进行排序然后合并。

在合并的时候会对两组数据进行比对，那么此时如果右边那一组的数据小于左边当前判断的这个数据，那么左边这组数据中后面的数据都能与右边当前判断的数据组成逆序对。

如图为归并排序中的一个过程

a: 1 6 7 8 9   b: 2 3 4 5 6
tmp: NULL
1 <= 2
tmp:1

6 > 2
res += 4 // (6,7,8,9 -> 2)
tmp:1 2

6 > 3
res += 4 // (6,7,8,9 -> 3)
tmp:1 2 3

6 > 4
res += 4 // (6,7,8,9 -> 4)
tmp:1 2 3
...

6 <= 6
tmp:1 2 3 4 5 6

7 > 6
res += 3 // (7,8,9 -> 6)
tmp:1 2 3 4 5 6 6
...

---

C++

#include 

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n;
int a[N];
int tmp[N];

ll merge_sort(int q[], int l, int r)
{
	if (l >= r) return 0;
	int mid = l + r >> 1;
	ll res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
    // 两个子区间排过序了,这些直接不会再有逆序对了,一起加到这一层
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r)
	{
		if (q[i] <= q[j]) tmp[k++] = q[i++];
		else // left部分的当前值大于right部分当前的值，那么left后面的都能与right当前值成为逆序对
		{
			res += mid - i + 1;
			tmp[k++] = q[j++];
		}
	}
	while (i <= mid) tmp[k++] = q[i++];
	while (j <= r) tmp[k++] = q[j++];
	for (int i = l, j = 0; i <= r; i++, j++)
		q[i] = tmp[j];
	return res;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	cout << merge_sort(a, 1, n) << endl;
	return 0;
}

树状数组

树状数组求逆序对思路比较简单，每次添加一个数的时候查找已经比这个数大的数有多少个，然后加到res里面即可，由于数据达到1e9，因此要离线存储所有数据然后离散化。

#include 
#include 
#include 

#define lowbit(x) x&-x

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<int> alls;

const int N = 3e5 + 10;
ll ans = 0;
int a[N], c[N];

void add(int x, int n)
{
	for (int i = x; i <= N; i += lowbit(i))
	{
		c[i] += n;
	}
}

int query(int x)
{
	int res = 0;
	for (int i = x; i > 0; i -= lowbit(i))
	{
		res += c[i];
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		alls.push_back(a[i]);
	}
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	for (int i = 1; i <= n; i++)
	{
		a[i] = lower_bound(alls.begin(), alls.end(), a[i]) - alls.begin() + 1;
		ans += query(N - 1) - query(a[i]);
		add(a[i], 1);
	}
	cout << ans << endl;
	return 0;
}