HDU 5775 Bubble Sort樹狀數(shù)組詳解

題面：

Bubble Sort Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 709????Accepted Submission(s): 418


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

for(int?i=1;ii;—j)
????????if(P[j-1]?>?P[j])
????????????t=P[j],P[j]=P[j-1],P[j-1]=t;

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 0HintIn 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. ?
Author FZU ?
Source 2016 Multi-University Training Contest 4

題意：

??? 給定一個1-N的隨機排列，對此序列進行冒泡排序，問在排序過程中，每個數(shù)到達過的最右端和最左端的差值。

解題：

??? 因為排序的具體過程是從右側開始，每次將當前最小的值移到最左端，故一個數(shù)會到達的最右位置是它的起始位置+其右側小于它的數(shù)字數(shù)量（在后面比他小的數(shù)向左移動的過程中，它會向右移動這么多步）。最左位置是其原來位置和排序之后應該處于的位置，兩者的小者。最后，兩個位置作差即為所求。

??? 關鍵點是在于如何統(tǒng)計一個數(shù)右側有幾個數(shù)比它小，可以從右往左遍歷，用樹狀數(shù)組維護，因為是邊移動邊統(tǒng)計的，每次就可以直接詢問【1-a[j]-1】的和，即為右側小于a[j]的數(shù)字的數(shù)量。

代碼：

#include#include#include#define?inf?1000000
using?namespace?std;
int?a[100010],c[100010],ans[100010];
int?t,n;
int?max(int?a,int?b)
{
	return?a>b?a:b;
}
int?min(int?a,int?b)
{
	return?a0)
	{
		res+=c[x];
		x-=lowbit(x);
	}
	return?res;
}
void?update(int?i,int?val)
{
	while(i<=n)
	{
		c[i]+=val;
		i+=lowbit(i);
	}
}
int?main()
{
	int?tmp,le,ri;
	scanf("%d",&t);
????for(int?i=1;i<=t;i++)
	{
		scanf("%d",&n);
		for(int?j=0;j=0;j--)
		{
???????????tmp=sum(a[j]);
		???update(a[j],1);
		???le=min(a[j]-1,j);
		???ri=j+tmp;
		???ans[a[j]]=ri-le;
		}
		printf("Case?#%d:",i);
		for(int?j=1;j<=n;j++)
			printf("?%d",ans[j]);
		printf("n");
	}
	return?0;
}