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 ,
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<cstdio>
#include<iostream>
using namespace std; int n;
const int maxn = 5e5+;
int num[maxn];
typedef long long ll; ll Mersort(int l,int r)
{
int mid = (l+r)/;
int i=l,j=mid+;
int b[r-l+];
int k=;
ll ans = ;
while(i <= mid && j <= r)
{
if(num[i] <= num[j])
b[k++] = num[i++];
else
b[k++] = num[j++],ans+=mid-i+;
}
while(i <= mid)
{
b[k++] = num[i++];
}
while(j <= r)
{
b[k++] = num[j++];
}
for(int i=l; i<=r; i++)
{
num[i] = b[i-l+];
}
return ans;
} int Merge(int l,int r,ll &ans)
{
int mid = (l+r)/;
if(l == r)
return ;
Merge(l,mid,ans);
Merge(mid+,r,ans);
ans += Mersort(l,r);
}
int main()
{
while(~scanf("%d",&n) && n)
{
for(int i=; i<=n; i++)
scanf("%d",&num[i]);
ll ans = ;
Merge(,n,ans);
printf("%lld\n",ans);
}
}
②树状数组：（要注意离散，离散可以二分，也可以map）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std; const int maxn = 5e5+;
int n;
int tree[maxn];
typedef long long ll; int lowbit(int x)
{
return x&(-x);
} void add(int x)
{
for(int i=x;i<=n;i+=lowbit(i))
{
tree[i]++;
}
} int Query(int x)
{
int ans = ;
for(int i=x;i>;i-=lowbit(i))
{
ans+=tree[i];
}
return ans;
}
int query(int x,int n,int *b)
{
return lower_bound(b+,b++n,x) - b;
}
int main()
{
while(~scanf("%d",&n) && n)
{
memset(tree,,sizeof(tree));
int a[n+],b[n+];
for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i] = a[i];
sort(b+,b++n);
int len = unique(b+,b++n)-b-;
ll ans = ;
for(int i=;i<=n;i++)
{
int pos = query(a[i],len,b);
add(pos);
ans += pos - - Query(pos-);
}
printf("%lld\n",ans);
}
}