【樹狀數組】HDU2838 Cow sorting

題意：

n頭母牛，每頭牛都有一個暴躁值，要求對這n頭母牛從小到大排序。

隻能進行對相鄰母牛的調換操作，每次調換要花費的時間等于這相鄰母牛暴躁值之和，求排序完之後所需要用的最短時間。

解析：

分析這麼個情況：4 5 6 2

按照排序，我們每次把最後的這個2往前調，這樣一共有3次調換，每次都會用到2，總共花費的時間是 3次* 2 + 數字2之前 所有大于它的數字之和 。

代碼tree數組有兩層，一層記錄前面大于它的數字的個數，另一層記錄前面大于他的數字之和。

記得用longlong

代碼：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int t,n,m,x,y,cnt=0;
ll tree[3][maxn];
ll ans;

void add(int i,int x,ll d){
	while(x<=maxn){
		tree[i][x] += d;
		x += lowbit(x);
	}
}

ll sum(int i,int x){
	ll sum = 0;
	while(x>0){
		sum+=tree[i][x];
		x -= lowbit(x);
	}
	return sum;
}

int main(){
	while(~scanf("%d",&n)){
		memset(tree,0,sizeof tree);
		ans = 0;
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			ll sum1=sum(1,maxn)-sum(1,x);
			ll sum2=sum(2,maxn)-sum(2,x);
			ans += sum1*x+sum2;
			add(1,x,1);
			add(2,x,x);
		}
		printf("%lld\n",ans);
	}
	return 0;
}