HDU - 5775 Bubble Sort(树状数组)

题目链接：点击查看

题目大意：给出n个数，求出按照冒泡排序期间每个数可以到达的最右边位置和最左边位置的差

题目分析：其实这个题想明白了就很简单了，先用辅助数组a按照顺序存储每一个数，a[i]就代表排序完的位置，i就代表排序前的位置，按照冒泡排序的规则，可以知道，任意位置可以到达的最左边的位置，就是它排序前和排序后的位置中的最小值，而可以到达最右边的位置是取决于其右边有几个比它本身小的数，可以用树状数组求逆序数的原理来求，其实这个题也可以颠倒思路，即最右端是a[i]和i中的最大值，最左端是取决于其左边有几个比它本身大的数，直接上代码了：

#include<iostream>
#include<cstdio> 
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<cmath>
using namespace std;

typedef long long LL;

const int inf=0x3f3f3f3f;

const int N=1e5+100;

int c[N];

LL l[N],r[N];

int n;

int lowbit(int x)
{
	return x&-x;
}

void update(int pos)
{
	while(pos<=n)
	{
		c[pos]++;
		pos+=lowbit(pos);
	}
}

LL query(int pos)
{
	LL ans=0;
	while(pos)
	{
		ans+=c[pos];
		pos-=lowbit(pos);
	}
	return ans;
}

int a[N];

int main()
{
//	freopen("input.txt","r",stdin);
	int w;
	cin>>w;
	int kase=0;
	while(w--)
	{
		memset(c,0,sizeof(c));
		memset(l,0,sizeof(l));
		memset(r,0,sizeof(r));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",a+i);
		for(int i=1;i<=n;i++)
		{
			l[a[i]]=min(i,a[i]);
		}
		for(int i=n;i>=1;i--)
		{
			r[a[i]]=i+query(a[i]-1);
			update(a[i]);
		}
		printf("Case #%d:",++kase);
		for(int i=1;i<=n;i++)
			cout<<' '<<abs(l[i]-r[i]);
		cout<<endl;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	return 0;
}