hdu 5775 Bubble Sort(树状数组求逆序数)

Problem Description
P is a permutation of the integers from 1 to N(index starting from 1).
Here is the code of Bubble Sort in C++.

After the sort, the array is in increasing order. ?? wants to know the absolute values of difference of rightmost place and leftmost place for every number it reached.

 

Input
The first line of the input gives the number of test cases T; T test cases follow.
Each consists of one line with one integer N, followed by another line with a permutation of the integers from 1 to N, inclusive.

limits
T <= 20
1 <= N <= 100000
N is larger than 10000 in only one case.

 

Output
For each test case output “Case #x: y1 y2 … yN” (without quotes), where x is the test case number (starting from 1), and yi is the difference of rightmost place and leftmost place of number i.

 

Sample Input
2
3
3 1 2
3
1 2 3
 Sample Output
Case #1: 1 1 2
Case #2: 0 0 0

Hint

In first case, (3, 1, 2) -> (3, 1, 2) -> (1, 3, 2) -> (1, 2, 3) the leftmost place and rightmost place of 1 is 1 and 2, 2 is 2 and 3, 3 is 1 and 3 In second case, the array has already in increasing order. So the answer of every number is 0.

冒泡排序,而且这个冒泡是从最右开始的,所以说如果一个数右边有比他的小的数,那他一定会一直往右移动,最后的位置一定是原先的位置pos+x(右边有x个数比他大,也就是相当于求个逆序数)。这也就是一个数的右边界。左边界就是一个数一开始的位置和他最后的位置二者的最小值。如果说一个数已经在它本应该在的位置,那么根据题目给的冒泡顺序肯定不可能再向左移动。

发表评论

电子邮件地址不会被公开。 必填项已用*标注