hdu 2838 Cow Sorting（樹狀數組）

真是得跪,,,我以前做的求逆序數若爆了，連芒果大神都對我無語了。嗚嗚嗚

這題和poj那道置換數很像，但是這題要求必須相鄰的數才能交換。這就可以用樹狀數組求數x之前比x大的數量和比x大的數的和。

以前隻是覺得在x之前插入，然後查詢的時候找比x大的，現在發現不對。

C1=a1

C2=a1+a2

C3=a3

C4=a1+a2+a3+a4

.....

樹狀數組隻能求0~N的和。比如 3 : sum+=a3,x-=lowbit(x) x=2 sum+=a1+a2.

插入的情況:比如插入3,就是說C3+1,x+=lowbit(3) x=4.C[4]+=1。。。。直到n.

/*
Problem ID:
meaning:
Analyzing:
*/
#include <iostream>
#include <algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<vector>

using namespace std;
typedef struct even{int y1,y2,x;}even;

#define clr(A,k) memset(A,k,sizeof(A))
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define LL long long
#define BUG puts("here!!!")
#define print(x) printf("%d\n",x)
#define STOP system("pause")
#define eps 1e-8
#define PI acos(-1.0)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 100005
#define lowbit(x) x&(-x)
LL gcd(LL a,LL b) {return a?gcd(b%a,a):b;}
int n;
typedef struct hdu{
    LL sum,cnt;
}hdu;
hdu C[maxn];
void update(int pos,int val){
    while(pos<maxn){
        C[pos].cnt++;
        C[pos].sum+=val;
        pos+=lowbit(pos);
    }
}
LL query1(int x){
    LL ret=0;
    while(x>0){
        ret+=C[x].cnt;
        x-=lowbit(x);
    }
    return ret;
}
LL query2(int x){
    LL ret=0;
    while(x>0){
        ret+=C[x].sum;
        x-=lowbit(x);
    }
    return ret;
}
int main(){
    while(cin>>n){
        clr(C,0);
        LL sum=0,x,k1=0,k2=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            update(x,x);
            k2=query2(maxn)-query2(x);
            k1=i-query1(x);
            if(k1!=0)
            sum+=k1*x+k2;
        }
        printf("%I64d\n",sum);
    }
return 0;
}