給定 N 個矩形,求它們聯集的周長。N ≤ 5000,坐標範圍需離散化。
周長 = 水平邊長總和 + 豎直邊長總和。兩者對稱,只需掃描兩次。
y1:cover = +1,區間 [x1, x2)y2:cover = -1,區間 [x1, x2)y 排序掃描線x 方向的總覆蓋長度 len|len[i] - len[i-1]|將 x, y 互換,重複上述過程,累加豎直邊長變化。
struct Edge { int l, r, h, f; }; // l,r: x區間; h: 掃描線座標; f: +1/-1
int c[MAXN]; // 離散化坐標數組
int cover[4*MAXN]; // 線段樹覆蓋計數
int len[4*MAXN]; // 線段樹維護的覆蓋長度
int lazy[4*MAXN]; // 延遲標記
void PushUp(int rt, int l, int r) {
if (lazy[rt])
sum[rt] = c[r+1] - c[l]; // 完全覆蓋,長度 = 離散化座標差
else if (l == r)
sum[rt] = 0; // 葉節點無覆蓋
else
sum[rt] = sum[rt<<1] + sum[rt<<1|1]; // 合併子節點
}
x 坐標離散化ans += |len - last|y 坐標離散化x↔y),再次掃描累加ansO(N log N)(排序 + 2N 次線段樹更新)O(N)erfen() 映射離散化索引f(+1/-1)而非布爾值,支援多層覆蓋c[] 留出 c[r+1] 邊界,避免越界