P5490 【模板】扫描线 矩形面积并 - 洛谷 (luogu.com.cn)#includebits/stdc.h using namespace std; typedef long long LL; #define lc(p) (p 1) #define rc(p) ((p 1) | 1) const int N 2e5 10; struct Line { int p; int st, ed; int flg; } L[N]; // 一条竖线x 坐标是 py 的范围是 st 至 ed int s[N * 2], cnt; struct trnode { int l, r, c; LL len; } tr[N 3]; bool cmp(Line la, Line lb) { return la.p lb.p; } void pushup(int p) { if (tr[p].c 0) { tr[p].len s[tr[p].r] - s[tr[p].l]; } else { tr[p].len tr[lc(p)].len tr[rc(p)].len; } } void bt(int p, int l, int r) { tr[p] {l, r, 0, 0}; if (l 1 r) { return ; } int mid (l r) 1; bt(lc(p), l, mid); bt(rc(p), mid, r); // 树里面是区间段不是点所以不用 r 1 } void change(int p, int l, int r, int c) { if (r s[tr[p].l] || l s[tr[p].r]) { // 相等的情况说明只是区间段的边界点擦边 // 并不代表区间段相交所以也要 return return ; } if (l s[tr[p].l] s[tr[p].r] r) { tr[p].c c; pushup(p); return ; } change(lc(p), l, r, c); change(rc(p), l, r, c); pushup(p); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; int xa, ya, xb, yb; for (int i 1; i n; i ) { cin xa ya xb yb; L[i] {xa, ya, yb, 1}; L[i n] {xb, ya, yb, -1}; s[i] ya; s[i n] yb; } n * 2; sort (s 1, s n 1); cnt unique(s 1, s n 1) - (s 1); sort (L 1, L n 1, cmp); bt(1, 1, cnt); LL ans 0; for (int i 1; i n; i ) { change(1, L[i].st, L[i].ed, L[i].flg); ans (L[i 1].p - L[i].p) * tr[1].len; } cout ans \n; return 0; }