题目链接：
?pid=2838
题目大意：
有N头奶牛排成一排。每头奶牛都有一个唯一的"坏脾气"值。坏脾气的范围为1~100000。现在将
奶牛重新排序，使奶牛按照坏脾气增加的顺序排列。所有的奶牛都可以相互交换位置。但是交换脾
气值为X，Y的两头奶牛，需要的时间是X+Y。现在问：将奶牛重新排列需要的最短时间是多少。
思路：
这道题就是给你一个N个元素的序列，求这个序列中所有逆序数的和。所以，对于值为a的第i个元素，
除了知道前i个元素里比a大的元素个数之外，还得知道前i个元素里比a大的元素的和。建立结构体树
状数组，一个变量来记录比a小的元素个数，，i -比a小的元素个数就是前i个元素里比a大的元素个数(即
逆序数的个数)，这样是为了方便计算。另一个变量来记录比a小的元素的和。n个数的和-比a小的元素
和就是之前比a大的数的和。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define LL __int64using namespace std;const int MAXN = 100010;struct Node{int Cnt; //记录前i个元素里比a大的元素个数LL sum;//记录前i个元素里比a大的元素的和}Tree[MAXN];int N;int Lowbit(int i){return i & (-i);}void Update(int i,int v,int Cnt){while(i <= N){Tree[i].sum += v;Tree[i].Cnt += Cnt;i += Lowbit(i);}}int QueryCnt(int n) //返回值为a的数前边比a小的元素个数{int ans = 0;while(n > 0){ans += Tree[n].Cnt;n -= Lowbit(n);}return ans;}LL QuerySum(int n) //返回值为a的数前边比a小的元素的和{LL ans = 0;while(n > 0){ans += Tree[n].sum;n -= Lowbit(n);}return ans;}int main(){int a;while(cin >> N){LL ans = 0;memset(Tree,0,sizeof(Tree));for(int i = 1; i <= N; ++i){cin >> a;Update(a,a,1);LL k1 = i – QueryCnt(a); //k1值为a的第i个元素的逆序对if(k1 != 0){//值为a的数之前比a大的数的总和LL k2 = QuerySum(N) – QuerySum(a);ans += k1*a + k2;}}cout << ans << endl;}return 0;}
不要做刺猬能不与人结仇就不与人结仇，
