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

Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536KTotal Submissions: 66796 Accepted: 25021

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 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

             这里要注意的两个点就是离散化操作和怎样理解   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; }