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.
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
Source
正解一：归并排序
解题报告：
大概题意是求数列的冒泡排序排序次数，求逆序对的模板题。
直接归并排序的时候统计一下就可以了。
归并排序的提交记录：
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
int n,m;
int jump[MAXN];
int g[MAXN];
LL ans; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void merge(int l,int mid,int r){
int i=l,j=mid+;
int cnt=l;
while(i<=mid && j<=r) {
if(jump[i]<=jump[j]) g[cnt++]=jump[i++];
else{
g[cnt++]=jump[j++];
//ans+=mid-i+1;
ans+=(LL)mid; ans-=(LL)i; ans++;
}
}
while(i<=mid) g[cnt++]=jump[i++];
while(j<=r) g[cnt++]=jump[j++];
//for(;i<=mid;i++) g[cnt++]=a[i];
//for(;j<=r;j++) g[cnt++]=a[i];
for(i=l;i<=r;i++) jump[i]=g[i];
} inline void gui(int l,int r){
if(l==r) return ;
int mid=(l+r)/;
gui(l,mid); gui(mid+,r);
merge(l,mid,r);
} inline void solve(){
while() {
n=getint();
if(n==) break;
for(int i=;i<=n;i++) jump[i]=getint();
ans=;
gui(,n);
printf(OT"\n",ans);
}
} int main()
{
solve();
return ;
}
正解二：树状数组
解题报告：
树状数组也是可做的。
由于数字比较大，先离散化一下，然后按顺序插入，插入之后看看已经有多少个数比自己大了，统计一下就可以了。
比归并排序慢好多哦。。。
| Run ID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 15602746 | ljh2000 | 2299 | Accepted | 7932K | 532MS | G++ | 1256B | 2016-06-10 15:41:43 |
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
int n,L;
LL ans;
int a[MAXN],u[MAXN];
int shu[MAXN],rank[MAXN]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void update(int x,int val){
while(x<=L) {
shu[x]+=val;
x+=x&(-x);
}
} inline LL query(int x){
LL total=;
while(x>) {
total+=shu[x];
x-=x&(-x);
}
return total;
} inline void solve(){
while() {
n=getint();
if(n==) break;
for(int i=;i<=n;i++) u[i]=a[i]=getint();
ans=;
memset(shu,,sizeof(shu));
sort(u+,u+n+);
L=unique(u+,u+n+)-u-;
for(int i=;i<=n;i++) {
rank[i]=lower_bound(u+,u+L+,a[i])-u;
update(rank[i],);
ans+=query(L)-query(rank[i]);
} printf(OT"\n",ans);
}
} int main()
{
solve();
return ;
}