# 逆序數對

#### 定義:
設一數列s[10]與其中兩index:i,j,當0<=i<j<=9 且s[i]>s[j]時,兩數被稱為逆序數對

#### 作法:
1. 掃一遍陣列 => 索引號i為嚴格遞增
2. 根據定義,只要找小於i的所有數中大於s[i]的個數就是當前的逆序數對個數
3. 掃完後把所有找到的逆序數對相加就是所有的逆序數對

#### 時間複雜度優化 :
在找前i個有幾個數比s[i]大時,可以利用BIT技巧計算
##### 比s[i]大的各數=BIT裡的數-BIT的query(比s[i]小的數)

int bit[MAXN];

void update(int n){
  while(n<=MAXN){
    bit[n]++;
    n+=n&-n;
  }
}

int query(int n){
  int sum=0;
  while(n>0){
    sum+=bit[n];
    n-=n&-n;
  }
  return sum;
}

int main(){
    ......
    int ans=0;
    for(int i=0;i<n;i++){
      ans+=i-query(s[i]);
      update(s[i]);
    }
}

#### 記憶體優化 :

離散化:
因為我們只要比大小,所以可以利用離散化把索引值壓縮到BIT的大小

sort(descrete.begin(),descrete.end());
for(int i=0;i<n;i++){
     arr[i]=lower_bound(descrete.begin(),descrete.end(),arr[i])-descrete.begin()+1;
    //+1是因為BIT的index要從1開始
}

#### 完整程式碼

#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;

int bit[MAXN]={0};

void update(int n){  //單點修改
  while(n<=MAXN){
    bit[n]++;
    n+=n&-n;
  }
}

int query(int n){  //前綴和查詢
  int sum=0;
  while(n>0){
    sum+=bit[n];
    n-=n&-n;
  }
  return sum;
}

int main(){
  int n;
  cin >> n;
  vector<int> arr(n);  //紀錄數列
  vector<int> descrete;  //利散化用
  
  for(int i=0;i<n;i++){
    cin >> arr[i];
    descrete.push_back(arr[i]);
  }
  
 //離散化
  sort(descrete.begin(),descrete.end());
  for(int i=0;i<n;i++){
    arr[i]=lower_bound(descrete.begin(),descrete.end(),arr[i])-descrete.begin()+1;
  }

  //BIT維護&計算答案
  int ans=0;
  for(int i=0;i<n;i++){
    ans+=i-query(arr[i]);
    update(arr[i]);
  }
  
  cout << ans << '\n';
  return 0;
}