Ultra-QuickSort 树状数组+离散化；

Description

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
<center> 9 1 0 5 4 , </center>
Ultra-QuickSort produces the output
<center> 0 1 4 5 9 . </center>
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

Output

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

             这里要注意的两个点就是离散化操作和怎样理解   ans += s - getsum(c[s]) + 1;这行代码所表达的内容；

             还有就是auto是c++ 14的内容，现在国内大多数oj是不支持的；（https://vjudge.net/problem/EOlymp-1303 在这里可以用auto）

             现在网上许多关于这道题的树状数组解答，基本没考虑过n个数中有同样的情况，他们大多是按照互不相同的n个数的条件来做的，可是这样考虑是不全面的，下面就是关于有相同的数的情况下的离散化操作；

             树状数组c开始的时候都初始化为0的，所以按照 9 1 0 5 4输入时，在进行离散化操作后也就会按照5 2 1 4 3的形式进行计算，5输入时，其他全是0，这时候getsum（5）=1；也就是说这时候不比5大的数的的数量之和是1（自己），因他而产生的逆序数就是0了；到输入4（离散化的4）的时候，c[1]=1,c[2]=2,c[3]=0,c[4]=1,所以getsum（4）=3，也就是在他之前的位置的不大于他的数的数量总和为3；这样依次进行计算即可。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
long long int m[500001];
int c[500001], n;
int tree[500001];
int lowbit(int x)
{
	return x&(-x);
}
int getsum( int x)
{
	long long int ans = 0;
	for (long long int s = x; s >= 1; s -= lowbit(s))
	{
//		cout << s << endl;
		ans += tree[s];
//		cout << s << " " << tree[s] << endl;
//		cout << ans << endl;
	}
	return ans;
}
void add( int x,  int d)
{
	for (long long int s = x; s <= n; s+=lowbit(s))
	{
		tree[s] += d;
	}
}
vector < long long  int > q;
void init()
{
	memset(tree, 0, sizeof(tree));
	memset(c, 0, sizeof(c));
	memset(m, 0, sizeof(m));
	q.clear();
}
int main()
{
	while (cin >> n&&n)
	{
		init();
		for (int s = 0; s < n; s++)
		{
			cin >> m[s];
			q.push_back(m[s]);
		}
		sort(q.begin(), q.end());
		auto siz = unique(q.begin(), q.end());
		for (int s = 0; s < n; s++)
		{
			c[s] = lower_bound(q.begin(), siz, m[s]) - q.begin() + 1;
		}
		long long int ans = 0;
		for (int s = 0; s < n; s++)
		{
			add(c[s], 1);
			ans += s - getsum(c[s]) + 1;
	//		cout << s + 1 - getsum(c[s]) << endl;
		}
		printf("%lld\n", ans);
	}
	return 0;
}