您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 1818 CQOI2010 內部白點：掃描線 + 樹狀數組求矩形交點數

編輯：關於C++

問題轉化

給定平面黑點，其餘為白點。白點若上下左右均有黑點則變黑。求最終黑點總數。等價於：黑點構成的水平、垂直線段（不含端點）的交點數 + 原黑點數。

掃描線 + BIT 算法

水平線段視為「修改」：在 y 掃描線到達時，區間 [x1+1, x2-1] 加 1
垂直線段視為「查詢」：拆為兩個前綴查詢 (x, y2-1) - (x, y1)
離線處理：所有事件按 y 排序，掃描線掃過
BIT 維护 x 軸覆蓋計數，查詢單點值即為該垂直線段經過的水平線段數

關鍵代碼片段

// Hash 版 BIT，避免離散化
struct HashBIT {
    struct Node { int key, val; Node* nxt; };
    Node* head[1001001];
    int& operator[](int key) {
        int pos = key % 1001001;
        for (Node* p=head[pos]; p; p=p->nxt) if (p->key==key) return p->val;
        return (head[pos]=new Node{key,0,head[pos]})->val;
    }
    void add(int x, int v) { for(;x;x-=x&-x) (*this)[x] += v; }
    int query(int x) { int r=0; for(;x<=2000000007;x+=x&-x) r+=(*this)[x]; return r; }
} bit;

// 構建水平線段（同 y、相鄰黑點間）
sort(points by y, then x);
for i=2..n if (p[i].y==p[i-1].y && p[i].x >= p[i-1].x+2)
    add_interval(p[i-1].x+1, p[i].x-1, p[i].y);

// 構建垂直查詢（同 x、相鄰黑點間）
sort(points by x, then y);
for i=2..n if (p[i].x==p[i-1].x && p[i].y >= p[i-1].y+2) {
    add_query(p[i].x, p[i-1].y, -1);
    add_query(p[i].x, p[i].y-1, +1);
}

// 掃描線處理
sort(intervals by y); sort(queries by y);
for each query:
    while (interval.y <= query.y) bit.add(interval.l, -1), bit.add(interval.r, +1), interval++;
    ans += bit.query(query.x) * query.flag;