0167-Bubble Sort

考え方
普通に指示通りに実装すれば答えを求めることが出来る。
が、それでは面白くないので蟻本を参考にBITを用いて書いてみた。(3/24追加)
実装(C++)

#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
struct BIT{
private:
	vector<int> bit;int size;
public:
	BIT(int n){
		size=n;bit=vector<int>(n+1);
	}
	//i番目の要素にxを加算する
	void add(int i,int x){
		i+=1;
		while(i<=size)bit[i]+=x,i+=i&-i;
	}
	int sum(int i){
		i+=1;int s=0;
		while(i>0)s+=bit[i],i-=i&-i;
		return s;
	}
};
int main(){
	for(int n;scanf("%d",&n),n;){
		int a[n],b[n],ans=0;
		BIT bit(n);
		for(int i=0;i<n;i++)scanf("%d",a+i),b[i]=a[i];
		std::sort(b,b+n);
		for(int i=0;i<n;i++)a[i]=lower_bound(b,b+n,a[i])-b;

		for(int i=0;i<n;i++){
			ans+=i-bit.sum(a[i]);
			bit.add(a[i],1);
		}
		printf("%d\n",ans);
	}

	return 0;
}