POJ 3067 Japan：樹狀數組統計高速公路交叉口數

題目大意

東岸 n 座城市（北到南 1..n），西岸 m 座城市（1..m）。k 條高速公路連接東岸 u 和西岸 v。兩條高速 (u1,v1), (u2,v2) 交叉 ⇔ `(u1-u2)*(v1-v2) < 0`。求交叉對數。多測試案例。

核心轉化：逆序對計數

• 按東岸城市 u 從大到小排序（或從小到大）。若 u 相同，按 v 從大到小排序（避免同 u 內部產生虛假逆序）。
• 依序處理每條高速，將其西岸城市 v 插入樹狀數組（BIT）。查詢 BIT 中 `< v` 的個數，即為與當前高速交叉的、且 u' > u 的高速數（因已處理的 u' ≥ u，同 u 時 v' > v 不交叉）。累加即為答案。

代碼

#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int MAXM = 1000000 + 100; // 西岸城市最大編號

struct Highway { int u, v; } hs[1000005];
int bit[1005]; // 西岸城市 m ≤ 1000

int lowbit(int x) { return x & -x; }
void add(int x, int v) { for (; x <= 1000; x += lowbit(x)) bit[x] += v; }
int sum(int x) { int s=0; for(;x>0;x-=lowbit(x)) s+=bit[x]; return s; }

bool cmp(const Highway& a, const Highway& b) {
    if (a.u != b.u) return a.u > b.u; // u 降序
    return a.v > b.v; // 同 u 時 v 降序
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n, m, k; scanf("%d%d%d", &n, &m, &k);
        for (int i = 0; i < k; ++i) scanf("%d%d", &hs[i].u, &hs[i].v);
        sort(hs, hs+k, cmp);
        memset(bit, 0, sizeof(bit));
        ll ans = 0;
        for (int i = 0; i < k; ++i) {
            ans += sum(hs[i].v - 1); // 查詢 v' < v 的個數
            add(hs[i].v, 1);
        }
        printf("Test case %d: %lld\n", cas, ans);
    }
    return 0;
}

複雜度

• 排序：O(k log k)。
• BIT 操作：O(k log m)。
• 總時間：O(k log k)，k ≤ 10⁵ 極快。

關鍵點

• **排序順序**：u 降序、同 u 時 v 降序，保證已處理高速的 u' ≥ u，且同 u 不產生交叉。
• **BIT 查詢前綴和** 統計 v' < v 的個數，對應交叉條件。
• **長長整數** 存儲答案（k≤10⁵，最大交叉對數 ≈ 5×10⁹，需 64 位）。

總結

POJ 3067 是「二維偏序對計數」的經典應用：排序一維 + BIT 統計另一維。高速公路交叉問題完美轉化為逆序對計數。BIT 代碼簡短、效率極高，是此類問題首選數據結構。