POJ 3067 Japan：高速公路交叉數計數（逆序對/樹狀數組）

題目

東岸 N 城市，西岸 M 城市，K 條高速連接 (東i, 西j)。高速為直線，求交叉點對數。最多兩條高速在同點交叉。N,M ≤ 1000, K ≤ N*M。

轉化為逆序對

按東岸城市編號升序排序，東岸相同按西岸升序。問題轉化為：在排序後的西岸序列中，求逆序對個數（即 i a[j] 的對數）。用樹狀數組 O(K log M) 統計。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXK = 1000000;
struct Edge { int u, v; } e[MAXK];
int bit[1005];

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

bool cmp(const Edge& a, const Edge& b) {
    if (a.u != b.u) return a.u < b.u;
    return a.v < b.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", &e[i].u, &e[i].v);
            e[i].u++; e[i].v++; // 1-based for BIT
        }
        sort(e, e+K, cmp);
        memset(bit, 0, sizeof(bit));
        long long ans = 0;
        for (int i = 0; i < K; i++) {
            ans += i - sum(e[i].v); // 已處理邊數 - 西岸 ≤ v 的數 = 西岸 > v 的數
            add(e[i].v, 1);
        }
        printf("Test case %d: %lld\n", cas, ans);
    }
    return 0;
}