树状数组计算逆序对（离散化）

本文总阅读量次

3013: Ultra-QuickSort

时间限制: 1 Sec 内存限制: 128 MB
题目描述
在这个问题中，你必须分析一个特定的排序算法。该算法通过交换两个相邻的序列元素直到序列按升序排序来处理一个连续的整数序列。对于输入序列
9 1 0 5 4，
Ultra-QuickSort产生输出
0 1 4 5 9。
您的任务是确定Ultra-QuickSort需要执行多少交换操作才能排序给定的输入序列。
输入
共n+1行
第1行：一个正整数n，（0< n <=500000）
第2~n+1行：每行一个整数a,(0 <= a <999,999,999)
输出
一个正整数，一个排序给定输入序列所需的最小交换操作数
样例输入
5
9
1
0
5
4
样例输出
6

提示

【数据范围】
对于30%的数据，(0< n <=10,000, 0<=a <10,000)
对于70%的数据，(0< n <=100,000, 0<=a<10,000,000)
对于100%的数据，(0< n<=500,000 0<=a<999,999,999)

【题目分析】
首先：因为题目中 $a [i]$ 可以到 $999, 999, 999$ 之多，在运用树状数组操作的时候，用到的树状数组 $C [i]$ 是建立在一个有点像位存储的数组的基础之上的，不是单纯的建立在输入数组之上。
比如输入一个 $9$ $1$ $0$ $5$ $4$ （最大 $9$ ），那么 $C [i]$ 树状数组的建立是在：
下标 0 1 2 3 4 5 6 7 8 9 –下标就要建立到9
数组 1 1 0 0 1 1 0 0 0 1 –通过1来表示存在
现在由于999999999这个数字相对于500000这个数字来说是很大的，所以如果用数组位存储的话，那么需要999999999的空间来存储输入的数据。这样是很浪费空间的，题目也是不允许的，所以这里想通过离散化操作。
离散化
那么怎么离散化操作呢？离散化是一种常用的技巧，有时数据范围太大，可以用来放缩到我们能处理的范围，必要的是建立一个结构体a[n]，v表示输入的值，order表示原i值，再用一个数组aa[n]存储离散化后的值
例如：

i：1 2 3 4 5     //i下标
v: 9 1 0 5 4     //v值

排序后:0 1 4 5 9 
order :3 2 5 4 1

如果建立映射： $a a [a [i] . o r d e r] = i$ ; 拍完序后,再按序号从小到大编号

排序后   :0 1 4 5 9 
order    :3 2 5 4 1 
aa[order]:1 2 3 4 5

原数据:9 1 0 5 4
aa    :5 2 1 4 3

即原本的9经过排序应该在第5位，现在aa[1]=5，对应原来的9，大小次序不变，只是将9缩小到了5
然后就可以利用树状数组维护前缀和的特点进行逆序对的求解：
假设扫描到aa[i]

离散后的数据插到树状数组中,add(aa[i],1)
求出1~aa[i]的数量，即小于等于aa[i]的个数且在aa[i]之前的,即非逆序的个数(包括自己)，因为当前总共插入i个数，所以比aa[i]大的数(它们在aa[i]插入之前,所以是逆序对)为i-sum(aa[i])
update为树状数组更新函数，sum为求出树状数组1~aa[i]的和。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int d,ps; 
	bool operator < (const node& rhs) const{
		return d < rhs.d;
	}
}a[500005]; 

int b[500005];
long long c[500005],n,ans;

void add(int v, int data)
{
    for(;v <= n;v += v & -v){
        c[v] += data;
    }
}


int sum(int x)
{
	int s = 0;
	for(;v > 0;v -= v&-v)
	    s += c[v];
	return s;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i].d;
		a[i].ps = i;
	}
	sort(a+1,a+1+n);
	int id = 0;
	for(int i = 1; i <= n; i++){ //根据位置，按顺序离散化
		if(i == 1 || a[i].d != a[i-1].d) id++;
		b[a[i].ps] = id;
	}
	for(int i = 1; i <= n; i++){
		add(b[i],1);
		ans += i - sum(b[i]);  //sum(b[i])表示之前有多少数小于或等于当前数字，剩下的则比它大，注意：比它大的数先出现
	}
	cout<<ans<<"\n";
	return 0;
}

【最后】
离散化的数据如果要还原，打个表吧，用空间换时间，时间复杂度O(1)