Language:
Ultra-QuickSort
Time Limit:7000MSMemory Limit:65536K
Total Submissions:45751Accepted:16615
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 sequence9 1 0 5 4 ,Ultra-QuickSort produces the output0 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
题意：求n个数的逆序对。
代码：
归并排序：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 501005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;ll a[maxn];ll b[maxn];ll n,ans;void Merge(ll a[],ll l,ll mid,ll r){int i,j,k=l;// int *b=new int[r+1]; //不要动态申请，会超时的FRE(i,l,r) b[i]=a[i];i=l;j=mid+1;while (i<=mid&&j<=r){if (b[i]<=b[j])a[k++]=b[i++];else{a[k++]=b[j++];ans+=(mid-i+1);}}while (i<=mid) a[k++]=b[i++];while (j<=r) a[k++]=b[j++];// delete []b;}void Merge_sort(ll a[],ll l,ll r){if (l>=r) return ;ll mid=(l+r)>>1;Merge_sort(a,l,mid);Merge_sort(a,mid+1,r);Merge(a,l,mid,r);}int main(){int i,j;while (scanf("%lld",&n),n){ans=0;FRE(i,1,n)scanf("%lld",&a[i]);Merge_sort(a,1,n);pf("%lld\n",ans);}return 0;}
树状数组：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 501005#define MAXN 2005#define mod 1000000009#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef __int64 ll;using namespace std;struct Node{int val;int pos;}node[maxn];int n;ll ans;int bit[maxn];int cmp(Node a,Node b){return a.val>b.val;}ll sum(int i){ll s=0;while (i>0){s+=bit[i];i-=i&-i;}return s;}void add(int i,int x){while (i<=n){bit[i]+=x;i+=i&-i;}}int main(){int i,j;while (scanf("%d",&n),n){FRE(i,0,n+10) bit[i]=0;FRE(i,1,n){scanf("%d",&node[i].val);node[i].val;node[i].pos=i;}sort(node+1,node+n+1,cmp);ans=0;FRE(i,1,n){ans+=sum(node[i].pos-1);add(node[i].pos,1);}pf("%I64d\n",ans);}return 0;}
，一直开到梦的尽头。你曾经说，
