HDOJ 5775 Bubble Sort

题目链接：HDOJ5775

分析这个题要求什么：L【i】和R【i】，意思是i出现的所有位置之中，最左边那个的坐标和最右边那个的坐标

题目中给的代码，是任意数字c，c会被其后面比c小的数字各交换一次，之后c就会只向前移动

如何求L【i】，很简单

L【a【i】】=min（i，a【i】）

在1到n的全排列时，对于每个数字来说，在冒泡排序中，结果唯一为1,2,3，……n

所以，每个数字的起始点为a【i】，终点为i，最左边的出现位置必为min（i，a【i】）

那么R【i】呢，需要知道，在原数组中有多少个比R【i】小的数，加上数字a【i】的原来位置，就是R【i】的值

那么，需要用线段树或者树状数组维护：当前数的右边有多少个比自己小的数

逆序先查询，后插入，就可以处理好

代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=1e5+10;
int a[maxn],c[maxn],L[maxn],R[maxn],n;

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

void update(int x,int add){
	while(x<=n){
		c[x]+=add;
		x+=LowBit(x);
	}
}

int getsum(int x){
	int ret=0;
	while(x){
		ret+=c[x];
		x-=LowBit(x);
	}
	return ret;
}

int main(){
	//freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			c[i]=0;
			L[a[i]]=min(i,a[i]);
		}
		for(int i=n;i>=1;i--){
			R[a[i]]=i+getsum(a[i]);
			update(a[i],1);
		}
		printf("Case #%d: ",Case);
		for(int i=1;i<=n;i++)
			printf("%d%c",R[i]-L[i],i==n?'\n':' ');
	}
	return 0;
}