一、Ultra-QuickSort

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,

Ultra-QuickSort produces the output
0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
很显然，求逆序对，我们将数据离散化，排序处理，变换成求正序对，利用树状数组求就行了，
例如
9 1 0 5 4
离散化（第几大）后就是
1 4 5 2 3（变成了求逆序数组的正序对）
逆序对为4+1+1=5

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int MX = 5e5 + 10;
ll a[MX], d[MX], c[MX], n;
bool cmp(int x, int y) {
	if (a[x] == a[y]) return x > y;
	else              return a[x] > a[y];
}
int lowbit(int x) {
	return x & (-x);
}

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

int query(int i) {
	int res = 0;
	while (i) {
		res += c[i];
		i -= lowbit(i);
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll res;
	while (cin >> n && n != 0) {
		memset(a, 0, sizeof a);
		memset(c, 0, sizeof c);
		res = 0;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			d[i] = i;
		}
		sort(d + 1, d + n + 1, cmp);
		for (int i = 1; i <= n; i++) {
			update(d[i],1);
			res += query(d[i]-1);
		}
		cout << res << endl;
	}

	return 0;
}

最后

以上就是虚幻高山最近收集整理的关于树状数组求逆序对一、Ultra-QuickSort的全部内容，更多相关树状数组求逆序对一、Ultra-QuickSort内容请搜索靠谱客的其他文章。