HDU 2838 COW SORTING [tree array] [data structure]

Subject link: http://acm.hdu.edu.cn/showproblem.php?pid=2838
——————————— ——————-.
Cow Sorting

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission( s): 3275 Accepted Submission(s): 1102

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.

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

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
2009 Multi-University Training Contest 3-Host by WHU

——————————— ——————-.

The main idea of ​​the topic:
You can know it mainly by the hint.
In fact, it is still a bubble sort, but the total cost is exchanged each time. Two worthy sums

The idea of ​​solving the problem:
First use a tree array to find the reverse logarithm before it appears.
For each number, its contribution to the result is
The sum of his previous inverse logarithm *a_i+ and his inverse number

Here we directly adopted the violent idea of ​​maintaining two tree arrays:
One maintains the number of inverse pairs
A maintenance of the sum of reverse ordinal numbers

Be careful to use I64, otherwise it will overflow…

Attachment Question code
————————————————————————.

#include #define abs(x) (((x) >0)?(x):-(x))#define lalal puts("*** ******")#define Rep(a,b,c) for(int a =(b);a<=(c);a++)#define Req(a,b, c) for(int a=(b);a>=(c);a--)#define span> Rop(a,b,c) for(int a=(b);a<(c);a++)#define s1(a) scanf("%d",&a)typedef long  long int LL;using namespace std; /** ************************************/const int N = 100000+5 ;#define lowbit(x) (x&-x)LL sum1[N], sum2[N];int cnt;void update1(int  index,int val){ for( int i=index;i<=cnt;i+=lowbit(i)) sum1[i]+=val; return ;}LL getSum1(< span class="hljs-keyword">int index){ LL ans=0; for(int i=index;i>0;i-=lowbit(i)) ans+=sum1 [i]; return ans;}void update2(int index,int val){ for(int i=index;i<=cnt;i+=lowbit(i)) sum2[i]+=val; return ;}LL getSum2(int index){ LL ans=0; for(int i=index;i>0;i-=lowbit(i)) ans+=sum2[i]; return ans;}int main(){ while(~s1(cnt)){ int x; LL ans=0; memset(sum1,0,sizeof(sum1)); memset(sum2,0,sizeof(sum 2)); Rep(i,1,cnt){ s1(x); ans+=x*(getSum2(cnt)-getSum2(x))+(getSum1 (cnt)-getSum1(x)); update1(x,x); update2(x,1);} printf("%I64d
",ans);} return 0;}