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.
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
题目地址
题目大意
给定一个序列求逆序数,用树状数组解决,注意数据太大需离散化处理
AC代码
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
const int M=500010;
int MN;
int e[M];
int k;
struct node
{
int val;
int pos;
}a[M];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int v)
{
for(;i<=MN;i+=lowbit(i)){
e[i]+=v;
}
}
int getsum(int i)
{
int res=0;
for(;i>0;i-=lowbit(i)){
res+=e[i];
}
return res;
}
bool cmp1(node a,node b)
{
return a.val<b.val;
}
bool cmp2(node a,node b)
{
return a.pos<b.pos;
}
void init()
{
sort(a+1,a+k+1,cmp1);
for(int i=1;i<=k;i++)
a[i].val=i;
sort(a+1,a+k+1,cmp2);
memset(e,0,sizeof(e));
MN=k;
}
int main()
{
//freopen("data.in","r",stdin);
long long res;
while(cin>>k&&k!=0){
res=0;
for(int i=1;i<=k;i++){
cin>>a[i].val;
a[i].pos=i;
}
init();
for(int i=1;i<=k;i++){
update(a[i].val,1);
res+=(i-getsum(a[i].val));
}
cout<<res<<endl;
}
}