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 5 9 1 0 5 4 3 1 2 3 0 Sample Output 6 0
树状数组求逆序数+离散化。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int MAXN=5e5+10000; typedef long long ll; int c[MAXN]; int b[MAXN]; int n; int lowbit(int x) { return x&(-x); } void add(int i,int x) { while(i<=MAXN) { c[i]+=x; i+=lowbit(i); } } int sum(int i) { int res=0; while(i>0) { res+=c[i]; i-=lowbit(i); } return res; } struct node { int v,pos; bool operator <(const node &W)const { return v<W.v; } }a[MAXN]; int main() { while(~scanf("%d",&n)&&n) { ll ans=0; memset(c,0,sizeof(c)); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { cin>>a[i].v; a[i].pos=i; } sort(a+1,a+1+n); memset(b,0,sizeof(b)); b[a[1].pos]=1; for(int i=2;i<=n;i++) { if(a[i].v==a[i-1].v) b[a[i].pos]=b[a[i-1].pos]; else b[a[i].pos]=i; } for(int i=1;i<=n;i++) { add(b[i],1); ans+=sum(n)-sum(b[i]); } cout<<ans<<endl; } }