Reference: http://blog.csdn.net/me4546/article/details/6333225
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2838
题目大意：每头牛有个愤怒值，每次交换相邻两个数进行升序排序，$cost=val_{1}+val_{2}$，求$\min \sum cost_{i}$
解题思路：
按输入顺序DP：
第i的值val的最小cost=当前数的逆序数个数*val+当前数的逆序数和
相当于每次只把这个val同逆序的数做交换，$\sum val_{1}=rev*val$ , $\sum val_{2}=\sum rev$
无后效性原则体现在，当前计算的cost只于前面的数有关，而且对顺序没有影响（逆序数随你怎么排了）
求逆序数个数和逆序数和都可以通过树状数组在$O(logn)$内完成
维护逆序数个数
树状数组对于每个val，$update(val,1)$，即每个val点的值是1
这样$rev=i-getIndex(val)$
原理是，树状数组是按从小到大维护的，输入顺序i（从1开始）-前面数个数（包含自身）=本来应该在后面，却跑到前面数的个数
维护逆序数和
本题的一个trick就是val不可重，所以$update(val,val)$ ，即每个val点的值是val
这样$\sum=getSum(n)-getSum(val)$，即整个序列已经更新的值和（i~n此时都是0)-当前值前面的和=逆序数和
代码
#include "cstdio"
#include "map"
#include "cstring"
#include "algorithm"
using namespace std;
#define LL long long
#define maxn 100005
LL sum[maxn],index[maxn];
int val,n;
int lowbit(int x) {return x&(-x);}
LL getSum(int x)
{
LL ret=;
while(x>)
{
ret+=sum[x];
x-=lowbit(x);
}
return ret;
}
LL getIndex(int x)
{
LL ret=;
while(x>)
{
ret+=index[x];
x-=lowbit(x);
}
return ret;
}
void update(int x,int s,int idx)
{
while(x<=n)
{
sum[x]+=s;
index[x]+=idx;
x+=lowbit(x);
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
memset(sum,,sizeof(sum));
memset(index,,sizeof(index));
LL ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&val);
update(val,val,);
LL rev=i-getIndex(val);
if(rev==) continue;
LL sum=getSum(n)-getSum(val);
ans+=(rev*val+sum);
}
printf("%I64d\n",ans);
}
}