# 逆序數對＆加總

## 題目敘述
>在一個長度為N的正整數序列$A$中，找出有多少個數對滿足 $Ai>Aj$ 且 $i<j$，並加總每個逆序數對中的兩個數的和
## 解題思路

### 1.Merge Sort

>$dc(l,r)$ 表示從 $Al$ 到 $Ar$ 中的逆序數對的總和
>
>$dc(l,r)=dc(l+m)+dc(m+1,r)+$橫跨左右的逆序數對總和

#### 如何求橫跨左右的逆序數對
>在合併左右序列時，比較兩序列最小的元素（因為分治的關係，兩序列已經是有序的）
>
>若右邊的比較小，代表這是一個逆序數對，且之後每一個左序列的元素皆可以跟這個元素形成逆序數對（因為有序）

    #define ll long long

    int num[1000005],tmp[1000005];
    
    int l,r,m;
    
    m=(l+r)/2;
    
    ll ans=0;
    
    ll i=l,j=m+1,sl=0,sm=0;
    //sm:目前取自右序列中的數值總和 
    //sl:目前取自右序列中的數的個數
    
    for(int a=l;a<=r;a++){
        
        if(i==(m+1)){ //左序列已取完
            tmp[a]=num[j];
            j++;  
        }
        
        else if(j==(r+1)){ //右序列已取完
            tmp[a]=num[i];
            ans+=num[i]*sl+sm;
            i++;
        }
        
        else if(num[i]<num[j]){ //左序列最小的元素較小
            tmp[a]=num[i];
            ans+=num[i]*sl+sm; 
            i++;
        }
        
        else{ //右序列最小的元素較小，更新sl及sr
            sl++;
            sm+=num[j];
            tmp[a]=num[j];
            j++;
        }
        
    }
    
    for(int a=l;a<=r;a++) num[a]=tmp[a];
    

#### 完整的程式碼

#include<iostream>
#define ll long long
using namespace std;

int num[1000005],tmp[1000005];
ll dc(int l,int r){

    if(l==r) return 0;
    
    if((l+1)==r){
    
        if(num[l]>num[r]){
        
            swap(num[l],num[r]);
            
            return (num[l]+num[r]);
            
        }
        
        return 0;
    }
    
    ll ans=0;
    
    int m=(l+r)/2;
    
    ans+=dc(l,m)+dc(m+1,r);//遞迴＋分治
    
    ll i=l,j=m+1,sl=0,sm=0;
    //sm:目前取自右序列中的數值總和 
    //sl:目前取自右序列中的數的個數
    
    for(int a=l;a<=r;a++){
        
        if(i==(m+1)){ //左序列已取完
            tmp[a]=num[j];
            j++;  
        }
        
        else if(j==(r+1)){ //右序列已取完
            tmp[a]=num[i];
            ans+=num[i]*sl+sm;
            i++;
        }
        
        else if(num[i]<num[j]){ //左序列最小的元素較小
            tmp[a]=num[i];
            ans+=num[i]*sl+sm; 
            i++;
        }
        
        else{ //右序列最小的元素較小，更新sl及sr
            sl++;
            sm+=num[j];
            tmp[a]=num[j];
            j++;
        }
        
    }
    
    for(int a=l;a<=r;a++) num[a]=tmp[a];
    
    return ans;
}

int main(){

    int N;
    
    cin>>N;
    
    for(int i=1;i<=N;i++) cin>>num[i];
    
    cout<<dc(1,N)<<endl;
    
}

### 2.BIT
>將原本的序列從$1$到$N$編號，由大到小排序後，從第一項（最大的那項）開始往後，並記錄現在比某個編號小的數有幾個，即$a[i]=$ 編號小於$i$的數有幾個，由於已經排序好了，因此到目前為止所記錄的數都會比自己大，編號比自己小的數也就可以與自己形成逆序數對

#### BIT的部分

struct BIT{

    ll a[1000005];
    
    int n;
    
    void ini(int _n){ //初始BIT陣列
        
        n=_n;
        memset(a,0,sizeof(a));
        
    }
    
    void add(ll x,ll v){ //更新BIT陣列，在每個有包含x的區間加上v
    
        while(x<=n){
        
            a[x]+=v;
            x+=(x)&(-x); //x&(-x)就是x的lowbit，也就是x在二進位制中最小的1
            
        }
        
    }
    
    ll ask(ll x){ //詢問小於等於x的區間
    
        ll r=0;
        
        while(x>0){
        
            r+=a[x];
            x-=(x)&(-x);
            
        }
        
        return n;
    }
}

#### 完整程式碼

>用pair儲存每個數的初始編號及數值

#include<iostream>
#include<vector>

#define ll long long 
#define F first
#define S second

bool cmp(pair<ll,ll> a , pair<ll,ll> b){ //自訂sort比較函式

    if(a.F!=b.F) return a.F>b.F; // 若數值不一樣，回傳較大的
    
    return a.S>b.S; // 否則就回傳編號較大的，因為若數值相同便不能成為逆序數對
}

struct BIT{

    ll a[1000005];
    
    int n;
    
    void ini(int _n){ //初始BIT陣列
        
        n=_n;
        memset(a,0,sizeof(a));
        
    }
    
    void add(ll x,ll v){ //更新BIT陣列，在每個有包含x的區間加上v
    
        while(x<=n){
        
            a[x]+=v;
            x+=(x)&(-x); //x&(-x)就是x的lowbit，也就是x在二進位制中最小的1
            
        }
        
    }
    
    ll ask(ll x){ //詢問小於等於x的區間
    
        ll r=0;
        
        while(x>0){
        
            r+=a[x];
            x-=(x)&(-x);
            
        }
        
        return n;
    }
    
}cnt,bit; // cnt記錄的是個數   bit記錄的是數值總和

int main() {

    int n;
    
    cin>>n;
    
    vector<pair<ll,ll> > v(n+5);
    
    for(int i=0;i<n;i++){
    
        cin>>v[i].F;
        v[i].S=i+1; //編號從1開始，若從0開始，lowbit將永遠都是0
        
    }
    
    bit.ini(n);
    cnt.ini(n);
    
    sort(v.begin(),v.end(),cmp);
    
    ll ans=0;
    
    for(int i=0;i<n;i++){
    
        ans += bit.ask(v[i].S-1) + // 數值大於且編號小於此數的數值總和
                v[i].F*cnt.ask(v[i].S-1); // 數值大於且編號小於此數的元素個數
        
        bit.add(v[i].S,v[i].F); // 更新數值
        
        cnt.add(v[i].S,1); // 更新個數
        
    }
    
    cout<<ans<<"\n";
    
    return 0;
}