# 資料結構題 - 低地距離 - APCS - by Peter Wang
## 題目資訊
此題為2020.10測驗中的題目3
###### tags: `APCS` `D&C` `BIT`

## 題目敘述
輸入一個長度為 2n 的陣列，其中 1 ~ n 的每個數字都剛好各 2 次。

i 的低窪值的定義是兩個數值為 i 的位置中間，有幾個小於 i 的的數字。

以 $[3, 1, 2, 1, 3, 2] 為例，1的低窪值為 0, 2 的低窪值值為 1, 3 的低窪值為 3。

請對於每個 1 ~ n 的數字都求其低窪值（兩個相同的數字之間有幾個數字比它小），輸出低窪值的總和，答案可能會超過 C++ int 的上限。

### 輸入：
第一行有一個正整數 n

第二行有 2n 個正整數，以空格分隔，保證 1 n 每個數字都恰好出現兩次。

### 輸出：
輸出 1 ~ n 每個數字的低窪值總和。

## 解題思路

## 程式碼

#include <iostream>
using namespace std;
#define ll long long
const int N = 200005;
int bit[N];
void add(int pos , ll val){
  while(pos<N){
    bit[pos]+=val;
    pos+=pos & (-pos);
  }
}
ll sum(int pos){
  ll ans=0;
  while(pos>0){
    ans+=bit[pos];
    pos-=pos & (-pos);
  }
  return ans;
}
int l[N],r[N];
int main(){
  int n;
  while(cin>>n){
    for(int i=1;i<=2*n;i++){
      int x;
      cin>>x;
      if(l[x]==0){
        l[x]=i;
      }
      else{
        r[x]=i;
      }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
      ans+=sum(r[i])-sum(l[i]);
      add(r[i],1);
      add(l[i],1);
    }
    cout<<ans<<endl;
  }
}

## 資料來源
[Zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=f315)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 9:58 AM]