Cow Sorting
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2185 Accepted Submission(s): 683
Problem Description
Sherlock's N (1 ≤ N ≤ 100,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage Sherlock's milking equipment, Sherlock would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes Sherlock a total of X + Y units of time to exchange two cows whose grumpiness levels are X and Y.
Please help Sherlock calculate the minimal time required to reorder the cows.
Input
Line 1: A single integer: N
Lines 2..N + 1: Each line contains a single integer: line i + 1 describes the grumpiness of cow i.
Lines 2..N + 1: Each line contains a single integer: line i + 1 describes the grumpiness of cow i.
Output
Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.
Sample Input
3
2
3
1
3
1
Sample Output
7
Hint
Input Details
Three cows are standing in line with respective grumpiness levels 2, 3, and 1.
Output Details
2 3 1 : Initial order.
2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4).
1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).
Source
Recommend
题意：
求逆序数两两的总和： 如 3 2 1 ：sum=(3+2)+(3+1)+(2+1)=12; 1 2 3: sum=0;
树状数组：
其实这题并不难，抓住一个点和熟悉树状数组大概就可以做出来了，那个点就是如何求得和。
这里才用的方法是参考别人的 ，自己想了一段时间没想出来。
对于新插入的一个元素，运用树状数组，可以求得比它小的元素的个数，比它小的元素的和，在它之前的元素的总和。
而对于每一个新元素，其sum[m]=m*(比它大的元素个数)+(前i个元素的和)-(比它小的元素的和)。
然后累加得解。
实现：
//46MS 2584K 955 B C++
#include<stdio.h>
#include<string.h>
#define ll __int64
#define N 100005
ll cnt[N],ssum[N],tsum[N];
inline ll lowbit(ll k)
{
return k&(-k);
}
void update(ll c[],ll k,ll detal)
{
for(;k<N;k+=lowbit(k))
c[k]+=detal;
}
ll getsum(ll c[],ll k)
{
ll s=;
for(;k>;k-=lowbit(k))
s+=c[k];
return s;
}
int main(void)
{
ll n,m;
while(scanf("%I64d",&n)!=EOF)
{
memset(cnt,,sizeof(cnt));
memset(ssum,,sizeof(ssum));
memset(tsum,,sizeof(tsum));
ll s=,temp=;
for(ll i=;i<=n;i++){
scanf("%I64d",&m);
update(cnt,m,);
update(ssum,m,m);
update(tsum,i,m);
temp=getsum(cnt,m-);
s+=m*(i-temp-);
s+=getsum(tsum,i-);
s-=getsum(ssum,m-);
//printf("**%I64d\n",s);
}
printf("%I64d\n",s);
}
return ;
}