# [树状数组] 树状数组基础练习题题解（四）

POJ-2299 Ultra-QuickSort

Time Limit: 7000MS
Memory Limit: 65536K

## 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


## Source

Waterloo local 2005.02.05

#include
#include
#include
#include
#include
#include
#define LL long long

using namespace std;

LL x = 0;
LL p = 1;
char ch = getchar();

while(ch < '0' || ch > '9'){
if(ch == '-')
p = -1;
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x*p;
}

const LL MAXN = 500000 + 10;

struct Data{
LL v;
LL id;
};

inline bool cmp(Data x,Data y){
return x.v < y.v;
}

Data input[MAXN*5];
LL tree[MAXN*5];
LL hash[MAXN*5];
LL n;

inline LL lowbit(LL x){
return x & (-x);
}

while(i<=n){
tree[i] += x;
i += lowbit(i);
}
}

inline LL sum(LL i){
LL ans = 0;

while(i){
ans += tree[i];
i -= lowbit(i);
}

return ans;
}

LL Sum;

int main(){

while(scanf("%lld",&n) && n){

memset(input,0,sizeof(input));
memset(hash,0,sizeof(hash));
memset(tree,0,sizeof(tree));
Sum = 0;

for(LL i=1;i<=n;i++){
input[i].id = i;
}

sort(input+1,input+n+1,cmp);

for(LL i=1;i<=n;i++)
hash[input[i].id] = i; //离散，从小到大重新编号

for(LL i=1;i<=n;i++){