低地距離 題解｜APCS 2020 年 10 月高級 第 4 題

前置知識

這題是「每個位置前面有幾個比它小」的經典題，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 樹狀陣列（Fenwick tree，常簡稱 BIT）：OI Wiki〈樹狀數組〉（簡體中文）——會「把某個位置加 \(1\)」與「問前綴總和」兩個操作、知道兩個都是 \(O(\log n)\) 就夠；本題把它當成「目前為止出現過哪些高度」的計數器。
• 數「前面有幾個比它小」：站上考古題反序數量數的是「前面有幾個比它大」，同一套機器，那題的題解用合併排序的分治來數；本題用樹狀陣列數，兩種都要會。
• 分治：NTUCPC Guide〈分治法〉、吳邦一《AP325》第 5 章的 P-5-4（教材 PDF 第 150～154 頁）——題目提示的第一種解法走這條路，收在最後的「另一種做法」。

簡潔題意

\(2n\) 座碉堡排成一列，高度 \(1\) 到 \(n\) 各恰好出現兩次。對每種高度 \(k\)，數兩座高度 \(k\) 的碉堡之間有幾座比 \(k\) 矮的，全部加起來（\(1 \le n \le 10^5\)；答案可能超過 \(2^{31}\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(n \le 1000\)。
• 子題組 2（\(40\) 分）：\(n \le 40000\)。
• 子題組 3（\(40\) 分）：無額外限制。

先拿下 20 分：照定義一座一座數

讀入時記下每種高度的兩個位置，對每種高度 \(k\) 掃過兩個位置之間的每一座，比 \(k\) 矮就加一。答案一開始就用 long long 存：題目明寫可能超過 \(2^{31}\)，巢狀排法 \(n, n-1, \ldots, 1, 1, \ldots, n\) 的答案是 \(n(n-1)\)，\(n = 10^5\) 時將近 \(10^{10}\)。

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

int main() {
    int n;
    cin >> n;
    vector<int> h(2 * n + 1);                        // 位置 1～2n
    vector<int> first(n + 1, 0), second(n + 1, 0);   // 每種高度的兩個位置
    for (int i = 1; i <= 2 * n; i++) {
        cin >> h[i];
        if (first[h[i]] == 0) first[h[i]] = i;
        else second[h[i]] = i;
    }
    long long total = 0;                             // 答案可能超過 2^31
    for (int k = 1; k <= n; k++) {
        for (int i = first[k] + 1; i < second[k]; i++) {
            if (h[i] < k) total++;                   // 夾在兩座 k 之間、而且比 k 矮
        }
    }
    cout << total << '\n';
    return 0;
}

每種高度要掃的格數是兩座之間的距離，最壞加起來約 \(n^2\)：\(n = 1000\) 瞬間；\(n = 40000\) 本站實測 \(0.5\)～\(2.1\) 秒，時限 \(1\) 秒，巢狀型的資料過不了；\(n = 10^5\) 最慢要 \(12\) 秒以上。子題組 1 穩拿，子題組 2 看資料長相，本站 \(20\) 筆計分測資有 \(8\) 筆超時。

從 20 分到 100 分：換個方向數——每個位置前面有幾座比它矮

把「兩座 \(k\) 之間比 \(k\) 矮的」換個算法。令 \(c(i)\) 是位置 \(i\) 前面（位置 \(1\) 到 \(i-1\)）比 \(h_i\) 矮的碉堡數。高度 \(k\) 的兩座在位置 \(p < q\)：\(c(q)\) 數的是位置 \(1\) 到 \(q-1\) 之間比 \(k\) 矮的，\(c(p)\) 數的是位置 \(1\) 到 \(p-1\) 之間比 \(k\) 矮的，相減正好剩下 \(p\) 到 \(q\) 之間的（位置 \(p\) 本身高度就是 \(k\)、不比 \(k\) 矮，扣不到它）：

圖 1 用範例 1 走一遍：\(c\) 值依序是 \(0, 1, 1, 1, 2, 0, 2, 6\)，高度 \(4\) 的兩座在位置 \(2\)、\(8\)，\(d(4) = 6 - 1 = 5\)。

所以答案 \(=\)（每種高度第二次出現的 \(c\)）的總和 \(-\)（第一次出現的 \(c\)）的總和。剩下的問題只有一個：由左到右掃過去，怎麼快速知道「前面有幾座比 \(x\) 矮」。用樹狀陣列當計數器——下標是高度，掃到高度 \(x\) 的碉堡就先問前綴和 countUpTo(x - 1)（這就是 \(c(i)\)），再把高度 \(x\) 那一格加一。每座碉堡一次查詢一次更新，\(2n\) 座共 \(O(n \log n)\)，\(n = 10^5\) 本站實測 \(0.05\) 秒。

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

int n;
vector<int> tree;                                    // 樹狀陣列：每一格管一段高度的「已出現次數」

void add(int x) {                                    // 高度 x 的碉堡又出現了一座
    for (; x <= n; x += x & -x) tree[x]++;
}
int countUpTo(int x) {                               // 目前為止出現過幾座高度 <= x 的碉堡
    int total = 0;
    for (; x > 0; x -= x & -x) total += tree[x];
    return total;
}

int main() {
    cin >> n;
    tree.assign(n + 1, 0);
    vector<bool> seen(n + 1, false);                 // 這種高度是不是已經出現過一次
    long long answer = 0;                            // 答案可能超過 2^31
    for (int i = 1; i <= 2 * n; i++) {
        int x;
        cin >> x;
        int lower = countUpTo(x - 1);                // c(i)：位置 i 前面有幾座比 x 矮的
        if (seen[x]) answer += lower;                // 第二次出現：加上 c(q)
        else answer -= lower;                        // 第一次出現：減掉 c(p)
        seen[x] = true;
        add(x);
    }
    cout << answer << '\n';
    return 0;
}

seen[x] 記這種高度是不是第二次出現：第一次減 \(c(p)\)、第二次加 \(c(q)\)。不必先把兩個位置存起來，讀一座處理一座。

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

// seq：只留下高度 lo～hi 的碉堡、保持原本的左右順序；回傳這些高度的低地距離總和
long long solve(const vector<int> &seq, int lo, int hi) {
    if (lo == hi) return 0;                          // 只剩一種高度：兩座之間不會有更矮的
    int mid = (lo + hi) / 2;                         // 高度 <= mid 算「矮組」、> mid 算「高組」
    vector<int> low, high;
    vector<int> firstSeen(hi - lo + 1, -1);          // 高組每種高度第一次出現時，前面有幾座矮組的
    long long total = 0;
    int lowCount = 0;                                // 目前為止看過幾座矮組碉堡
    for (int x : seq) {
        if (x <= mid) {
            low.push_back(x);
            lowCount++;
        } else {
            high.push_back(x);
            if (firstSeen[x - lo] == -1) firstSeen[x - lo] = lowCount;
            else total += lowCount - firstSeen[x - lo];   // 兩座 x 之間有幾座矮組的
        }
    }
    return total + solve(low, lo, mid) + solve(high, mid + 1, hi);
}

int main() {
    int n;
    cin >> n;
    vector<int> h(2 * n);
    for (int &x : h) cin >> x;
    cout << solve(h, 1, n) << '\n';
    return 0;
}

測過再交：範例沒有「比它高的夾在中間」

兩個範例只有巢狀（範例 1）和答案 \(0\)（範例 2）。沒蓋到：\(n = 1\)、比它高的碉堡夾在中間不能算、同一種矮高度兩座都要算、矮的都在前面不在兩座之間、答案超過 \(2^{31}\)。

七筆都親眼看過正確，這題就穩了。