hdu2838 Cow Sorting 樹狀數組

7 口碑商家客流量預測大賽》

Cow Sorting Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3322    Accepted Submission(s): 1118 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

get到新技巧就是樹狀數組不僅可以用來統計前面有多少個玩意兒比自己小等于，那幾個玩意兒的值也是可以記錄的，想象成大數組打标記一樣。。。幾天沒敲電腦現在啥話也憋不出來。。。

/*
 ━━━━━┒
 ┓┏┓┏┓┃μ'sic foever!!
 ┛┗┛┗┛┃＼○／
 ┓┏┓┏┓┃ /
 ┛┗┛┗┛┃ノ)
 ┓┏┓┏┓┃
 ┛┗┛┗┛┃
 ┓┏┓┏┓┃
 ┛┗┛┗┛┃
 ┓┏┓┏┓┃
 ┛┗┛┗┛┃
 ┓┏┓┏┓┃
 ┃┃┃┃┃┃
 ┻┻┻┻┻┻
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
using namespace std;
const int maxn=1e5+10;
long long save[maxn];
struct unit{
    int pos;
    long long val;
}c[maxn];
int n;
int lowbit(int x){
    return x&(-x);
}
void update(int x,int num,long long val){
    while(x<=maxn){
        c[x].pos += num;
        c[x].val += val;
        x += lowbit(x);
    }
}
long long getsum(long long x){
    long long sum=0;
    while(x){
        sum += c[x].pos;
        x -=lowbit(x);
    }
    return sum;
}
long long getVal(int x){
    long long sum = 0;
    while(x){
        sum += c[x].val;
        x -= lowbit(x);
    }
    return sum;
}
int main(){
    int i,j;
    long long ans;
    while(~scanf("%d",&n)){
        ans = 0;
        for(i=1;i<=n;i++){
            scanf("%lld",&save[i]);
        }
        for(i=n;i>=1;i--){
            //cout<<getsum(save[i])<<"  "<<getVal(save[i])<<endl;
            ans += getsum(save[i])*save[i] + getVal(save[i]);
            update(save[i], 1, save[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}