离散化 树状数组 求逆序数

缘起

一个序列的逆序数的定义是所有元素的逆序值之和. 而一个元素的逆序值的定义是

a[1,…,n] 中 a[i]的逆序值是a[i+1,…,n]中比a[i]严格小的元素的个数.

分析

这个怎么和树状数组联系到一起? 我们看一个数组，4 3 1 2， 则他的逆序数怎么求呢?

举个例子

4 3 2 1 这样一个数组, 我们先开一个数组b[N], 伊始全部是0, b[i] = 0 表示i尚未出现, 1表示已经出现了. 则4来了之后, b[4] = 1; 4的逆序数就是 b[5,…,]中1的个数（显然是0）. 因为这个范围中为1的话, 就表示在4之前已经出现了，而且它还比4来的大. 那么它当然和4构成逆序数. 下面3来了, b[3] = 1, 则3的逆序数就是 b[4,…,4]中1的个数. 这里显然是1, 即3的逆序数就是1, 下面2来了, 则b[2] =1, 则2的逆序数就是[3,4]中1的个数，显然是2, 最后1来了, 则1的逆序数就是[2,3,4]中1的个数, 显然是3, 所以根据逆序数的定义, 整个序列的逆序数就是 1+2+3=6. 所以我们看到, 其实就是b的部分和, 所以我们需要在logn时间内求出它. 而不能暴力的在O(n)时间内求出, 不然的话, 暴力算法是 O(n^2)的, n一旦为10^5, 则暴力算法就承受不住. 而树状数组是在logn时间内求出部分和的良好工具. 所以树状数组被自然的引进来了. 其次一个小问题是，如果数组的元素的范围变化范围较大的话，我们需要使用较大的空间进行hash, 就比较浪费, 对付它的工具就是离散化. 综合上述原理，我们不难写出如下程序

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <algorithm>
using namespace std;
//#define LOCAL
const int MAX_N = 100000+5;
typedef long long LL;
int a[MAX_N], d[MAX_N], c[MAX_N], n; // a是原数组 n是数组元素个数, d是a的离散化之后, c是分析中的树状数组, 0索引都不用于存储数据, n是数组元素个数

int unique(int *b, int n) // 去重b, n是b的元素个数,b已经非降
{
	int i,j;
	for (i = 1,j=1; i<=n; i++)
	{
		if (b[i] > b[j])
		{
			b[++j] = b[i];
		}
	}
	return j;
}

int search(int x, int *a, int n) // a是没有严格递增的n个元素的数组, x在a中也存在, 找出x的索引
{
	int lo = 1, hi = n+1; // [lo, hi)
	while (lo < hi)
	{
		int mi = (lo+hi)>>1;
		x<a[mi]?hi=mi:lo=mi+1; // 维持了左闭右开
	}
	return --lo; // 返回<=x的最大索引
}

void discrete(int *x, int *a, int n) // 将a离散化为x, n是数组元素个数
{
	int b[MAX_N];
	//memcpy(b+1, a+1, sizeof(int)*n);
	for (int i = 1; i<=n; i++)
	{
		b[i] = a[i];
	}
	sort(b+1,b+n+1);
	int res = unique(b, n); // b[1,...,res] 是用于离散化的工具
	for (int i = 1; i<= n; i++)
	{
		x[i] = search(a[i],b ,res); // 二分求解a[i]在b[0,...,res) 中的排名, 则离散化了a
	}
}

int lowbit(int x){return x&(-x);}

void update(int x, int val)
{
	while (x <= n)
	{
		c[x] += val;
		x+=lowbit(x);
	}
}

LL partialsum(int x)
{
	LL sum = 0;
	while (x)
	{
		sum += c[x];
		x-=lowbit(x);
	}
	return sum;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out","w", stdout);
#endif
	LL ret = 0;
	scanf("%d", &n);
	for (int i = 1; i<=n;scanf("%d", a+i),i++);
	discrete(d,a,n); // 离散化a的结果进入d中
	for (int i = 1; i<=n;i++)
	{
		ret+= partialsum(n) - partialsum(d[i]); // 因为要求的是 d[i]+1,...,n中1的个数 所以是相减
		update(d[i], 1);
	}
	printf("%lld\n", ret);

#ifdef LOCAL
	fclose(stdin);
#endif
	return 0;
}

此题是牛客网上的一道题目 https://www.nowcoder.com/acm/contest/77/A

ac情况

通过

您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例