POJ 3067：利用樹狀數組求逆序數解決線段相交問題

問題背景

給定兩條線段的端點 (x1, y1) 與 (x2, y2)，若滿足 x1 < x2 && y1 > y2 或 x1 > x2 && y1 < y2，則兩線段相交。本題要求計算所有相交線段對的數量。

解題思路

1. 將所有線段按東側端點 x 升序排序；x 相同時，按西側端點 y 升序排序。
2. 依序處理每條線段，利用樹狀數組（Binary Indexed Tree）維護已處理線段的西側端點分布。
3. 對於當前線段的西側端點 y，查詢樹狀數組中大於 y 的端點數量，即為與該線段相交的線段數。累加所有查詢結果即得答案。

核心代碼

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAXH 1005
using namespace std;

int n, m, k;
struct mem { int x, y; } a[MAXH*MAXH];
int c[1005];

bool cmp(mem a, mem b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
int lowbit(int x) { return x & (-x); }
void add(int x) {
    while (x <= m) { c[x]++; x += lowbit(x); }
}
int sum(int x) {
    int s = 0;
    while (x > 0) { s += c[x]; x -= lowbit(x); }
    return s;
}
int main() {
    int t; scanf("%d", &t);
    for (int kk = 1; kk <= t; ++kk) {
        memset(c, 0, sizeof(c));
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0; i < k; ++i) scanf("%d %d", &a[i].x, &a[i].y);
        sort(a, a + k, cmp);
        long long ans = 0;
        for (int i = 0; i < k; ++i) {
            ans += sum(m) - sum(a[i].y);
            add(a[i].y);
        }
        printf("Test case %d: %lld\n", kk, ans);
    }
    return 0;
}

複雜度分析

排序 O(k log k)，每次查詢與更新 O(log m)，總時間 O(k log m)，空間 O(m)，完全滿足題目限制。