Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 50517		Accepted: 18534

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.

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.

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.

5

9

1

0

5

4

3

1

2

3

0

6

0
题解：归并排序注意对dt主数组的更改，由于数据太大999999999所以要离散化
归并：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

typedef long long LL;

#define mem(x,y) memset(x,y,sizeof(x))

#define T_T while(T--)

#define F(i,x) for(i=1;i<=x;i++)

#define SI(x) scanf("%d",&x)

#define SL(x) scanf("%lld",&x)

#define PI(x) printf("%d",x)

#define PL(x) printf("%lld",x)

#define P_ printf(" ")

const int MAXN=500010;

int dt[MAXN],b[MAXN];

LL ans;

void mergesort(int l,int mid,int r){

	int ll=l,rr=mid+1,pos=l;

	while(ll<=mid&&rr<=r){

		if(dt[ll]<=dt[rr])b[pos++]=dt[ll++];

		else{

			ans+=rr-pos;

			b[pos++]=dt[rr++];

		}

	}

	for(int i=ll;i<=mid;i++)b[pos++]=dt[i];

	for(int i=rr;i<=r;i++)b[pos++]=dt[i];

	for(int i=l;i<=r;i++)dt[i]=b[i];

}

void ms(int l,int r){

	if(l<r){

		int mid=(l+r)>>1;

		ms(l,mid);

		ms(mid+1,r);

		mergesort(l,mid,r);

	}

}

int main(){

	int N;

	while(~scanf("%d",&N),N){

		int i,j;

		ans=0;

		F(i,N)

			SI(dt[i]);

			ms(1,N);

		PL(ans);puts("");

	}

	return 0;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

typedef long long LL;

#define mem(x,y) memset(x,y,sizeof(x))

#define T_T while(T--)

#define F(i,x) for(i=0;i<x;i++)

#define SI(x) scanf("%d",&x)

#define SL(x) scanf("%lld",&x)

#define PI(x) printf("%d",x)

#define PL(x) printf("%lld",x)

#define P_ printf(" ")

const int MAXN=500010;

int a[MAXN],b[MAXN],tree[MAXN+1];

LL ans;

int lowbit(int x){return x&(-x);}

void add(int x){

	while(x<=MAXN){

		tree[x]++;

		x+=lowbit(x);

	}

}

int sum(int x){

	int sm=0;

	while(x>0){

		sm+=tree[x];

		x-=lowbit(x);

	}

	return sm;

}

int main(){

	int N;

	while(~scanf("%d",&N),N){

		int i,j;

		mem(tree,0);

		F(i,N)SI(a[i]),b[i]=a[i];

		sort(b,b+N);

		ans=0;

		F(i,N){

			int pos=lower_bound(b,b+N,a[i])-b;

			ans+=i-sum(pos);

			add(pos+1);

		}

		PL(ans);puts("");

	}

	return 0;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

typedef long long LL;

#define mem(x,y) memset(x,y,sizeof(x))

#define T_T while(T--)

#define F(i,x) for(i=0;i<x;i++)

#define SI(x) scanf("%d",&x)

#define SL(x) scanf("%lld",&x)

#define PI(x) printf("%d",x)

#define PL(x) printf("%lld",x)

#define P_ printf(" ")

const int MAXN=500010;

int tree[MAXN+1];

LL ans;

int lowbit(int x){return x&(-x);}

struct Node{

	int v,p;

	friend bool operator < (Node a,Node b){

		return a.v<b.v;

	}

}a[MAXN];

void add(int x){

	while(x<=MAXN){

		tree[x]++;

		x+=lowbit(x);

	}

}

int sum(int x){

	int sm=0;

	while(x>0){

		sm+=tree[x];

		x-=lowbit(x);

	}

	return sm;

}

int main(){

	int N;

	while(~scanf("%d",&N),N){

		int i,j;

		mem(tree,0);

		F(i,N)SI(a[i].v),a[i].p=i;

		sort(a,a+N);

		ans=0;

		F(i,N){

			ans+=i-sum(a[i].p);

			add(a[i].p+1);

		}

		PL(ans);puts("");

	}

	return 0;

}