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.
until the sequence is sorted in ascending order. For the input sequence
Ultra-QuickSort produces the output
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.
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
Source
树状数组求逆序数....再加个离散化
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int tree[500010]; int val[500010]; int n; struct node { long long val; int index; }arr[500010]; int cmp(node a,node b) { return a.val < b.val; } inline int lowbit(int x) { return x&(-x); } void add(int x,int val) { for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=val; } long long sum(int x) { long long ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tree[i]; return ans; } int main() { while(~scanf("%d",&n),n) { for(int i=1;i<=n;i++) { scanf("%d",&arr[i].val); arr[i].index=i; } sort(arr+1,arr+n+1,cmp); for(int i=1;i<=n;i++) { if(i==1) val[arr[i].index]=i; else { if(arr[i].val==arr[i-1].val) val[arr[i].index]=val[arr[i-1].index]; else val[arr[i].index]=i; } } long long ans=0; memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++) { add(val[i],1); ans+=i-sum(val[i]); } printf("%lld\n",ans); } return 0; }