Ultra-QuickSort
Time Limit: 7000MS
Memory Limit: 65536K
Total Submissions: 27736
Accepted: 9946
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
59105431230
Sample Output
60
Source
Waterloo local 2005.02.05
这就是题求逆序数的题：方法有多种，最简单的用归并排序
我用的是树状数组；题目明显直接建树是不行的，因此得将其数变小，因此，用来两次快排
有个陷阱，和数据会超，得用long long 我就是因为这被ＷＡ了几次
#include<cstdio>#include<algorithm>#include<cstring>#define N 500004using namespace std;int M;long long f[N];int s[N];class node{ public: int num; int p;}root[N];int lowbit(int n){ return n&(-n);}void add(int s){ while(s<=M) { f[s]++; s+=lowbit(s); }}long long query(int num){ long long sum=0; while(num>0) { sum+=f[num]; num-=lowbit(num); } return sum;}bool cmp(node a,node b){ return a.num<b.num;}bool cmpp(node a,node b){ return a.p<b.p;}int main(){ int a; while(scanf("%d",&M)&&M) { memset(f,0,sizeof(f)); long long sum=0; for(int i=0;i<M;i++) { scanf("%d",&root[i].num); root[i].p=i; } stable_sort(root,root+M,cmp); for(int i=0;i<M;i++) root[i].num=i+1; stable_sort(root,root+M,cmpp); for(int i=0;i<M;i++) { add(root[i].num); sum+=query(M)-query(root[i].num); } printf("%lld\n",sum); }}