2014
02-17

# Cow Sorting

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.

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.

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.

3
2
3
1

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).


#include<iostream>
using namespace std;
#define N 100001
int n;
struct node
{
int index;
__int64 sum;
}c[N];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int k,int s)
{
while(x<=n)
{
c[x].index+=k;
c[x].sum+=s;
x+=lowbit(x);
}
}
int getsum_index(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x].index;
x-=lowbit(x);
}
return ans;
}
__int64 getsum_sum(int x)
{
__int64 ans=0;
while(x>0)
{
ans+=c[x].sum;
x-=lowbit(x);
}
return ans;
}
int main(void)
{
while(~scanf("%d",&n))
{
int i;

__int64 ans=0;
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
update(x,1,x);
__int64 k1=i-getsum_index(x);
if(k1!=0)
{
__int64 k2=getsum_sum(n)-getsum_sum(x);
ans=ans+k1*x+k2;
}

}
printf("%I64d/n",ans);
}
}