HDU - 2838 Cow Sorting （樹狀數組）

題意：求排列成升序的花費，每次隻能交換相鄰的兩個數，且話費為兩個數字的和，求最小的話費

思路：先設想一下，每個數字會被交換的可能，一個是目前面有大于它的數字，一個是當後面有小于它的數字兩種情況，這樣我們就可以聯想到樹狀數組了，每次看看該數面有多少小于它的，就可以求出多少大于它的了，然後倒着求小于它的情況，起初一直挖，改着改着就A了，還有太大的數組一定要定義成全局變量

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
#define ll long long 

ll num[MAXN],b[MAXN],c[MAXN];
ll ans;
int n;

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

void add(ll a[],ll pos,ll val){
	while (pos <= MAXN){
		a[pos] += val;
		pos += lowbit(pos);
	}
}

ll sum(ll a[],ll pos){
	ll tmp = 0;
	while (pos > 0){
		tmp += a[pos];
		pos -= lowbit(pos);
	}
	return tmp;
}

int main(){
	while (cin >> n){
		memset(c,0,sizeof(c));
		memset(b,0,sizeof(b));
		memset(num,0,sizeof(num));
		ans = 0;
		for (int i = 1; i <= n; i++){
			cin >> num[i];
			add(c,num[i],1);
			ans += num[i] * (i-sum(c,num[i]));
		}
		for (int i = n; i >= 1; i--){
			ans += num[i] * (sum(b,num[i]-1));
			add(b,num[i],1);
		}
		cout << ans << endl;
	}
	return 0;
}