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

5
9
1
0
5
4
3
1
2
3
0

6
0

# 题解

• 求逆序对数目
• 开一个大小为这些数的最大值的树状数组，并全部置0。从头到尾读入这些数，每读入一个数就更新树状数组，查看它前面比它小的已出现
• 过的有多少个数
• sum，然后用当前位置减去该sum，就可以得到当前数导致的逆序对数了。把所有的加起来就是总的逆序对数。
• 然而问题来了，数据最大999999999，显然开不下
• 解决方法是离散化一下