簡易題敘#
輸入一個長度為 \(2n\) 的陣列 ( \(1 \le n \le 10^5\) )，其中 \(1\) 到 \(n\) 的每個數字都剛好各 2 次。 \(i\) 的低窪值的定義是兩個數值為 \(i\) 的位置中間，有幾個小於 \(i\) 的的數字。
以 [3, 1, 2, 1, 3, 2] 為例，1 的低窪值為 0, 2 的低窪值值為 1, 3 的低窪值為 3。
請對於每個 \(1\) 到 \(n\) 的數字都求其低窪值（兩個相同的數字之間有幾個數字比它小），輸出低窪值的總和，答案可能會超過 C++ int 的上限。
範例測資：
- 輸入
3
3 1 2 1 3 2
- 輸出
4
概念講解#
這題我們可以嘗試用 BIT 來解。如果對 BIT 概念不熟的話，可以先看看這篇文章。
因為低窪值的定義是兩數間比它小的數的數量，所以我們可以透過事先記錄每個數字出現的位置，再從小的數字開始在這些紀錄好的位置上做記號：
for (int i = 1, t; i <= 2 * n; i++) {
cin >> t;
if (pos[t].first == 0) {
pos[t].first = i;
} else {
pos[t].second = i;
}
}
這樣一來，兩數之間的記號都是比它小的數字打上去的，也就是說，只要知道兩數間記號的數量，就等於知道了低窪值。而這樣需要單點加值 ( 在紀錄好的位置上做記號 )、區間求和 ( 求兩數間記號數量 ) 的特性，正符合 BIT 支援的功能。每次總低窪值都要加上兩數中間 ( 不含兩端！！！ ) 的記號數：
ans += sum(pos[i].second - 1) - sum(pos[i].first); // pos[i].second - 1 要特別注意，不要忘記兩數不包含在低窪裡
算完之後不要忘記幫兩端打上記號：
add(pos[i].first);
add(pos[i].second);
範例程式碼#
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 5;
pii pos[N];
int n, ans, bit[N];
void add(int id) {
for (int i = id; i <= 2 * n; i += i & -i) {
bit[i]++;
}
}
int sum(int id) {
int ans = 0;
for (int i = id; i > 0; i -= i & -i) {
ans += bit[i];
}
return ans;
}
signed main() {
cin >> n;
for (int i = 1, t; i <= 2 * n; i++) {
cin >> t;
if (pos[t].first == 0) {
pos[t].first = i;
} else {
pos[t].second = i;
}
}
for (int i = 1; i <= n; i++) {
ans += sum(pos[i].second - 1) - sum(pos[i].first);
add(pos[i].first);
add(pos[i].second);
}
cout << ans;
return 0;
}
