题目：给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
分析：在求面积并的基础上增加了一个成员len2，记录被覆盖至少两次的长度，num标记表示这一部分至少被全覆盖了几次（num = 1不一定代表这一段覆盖了只覆盖一次，还要看子节点）。同时考虑离散化。
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 2010; 4 struct edge 5 { 6 double x1, x2, h; 7 int flag; 8 edge(double a = 0, double b = 0, double c = 0, int d = 0) : x1(a), x2(b), h(c), flag(d){} 9 bool operator< (const edge& b)const 10 { 11 return h < b.h; 12 } 13 }e[maxn]; 14 15 struct node 16 { 17 int l, r; 18 double len1, len2; 19 int num; 20 node(int a = 0, int b = 0, double c = 0, double d = 0, int e = 0) : l(a), r(b), len1(c), len2(d), num(e){} 21 }t[maxn << 2]; 22 double x[maxn]; 23 24 void pushup(int tar) 25 { 26 if (t[tar].num) 27 t[tar].len1 = x[t[tar].r + 1] - x[t[tar].l]; 28 else if (t[tar].l == t[tar].r) 29 t[tar].len1 = 0; 30 else t[tar].len1 = t[tar << 1].len1 + t[tar << 1 | 1].len1; 31 if (t[tar].num >= 2) 32 t[tar].len2 = x[t[tar].r + 1] - x[t[tar].l]; 33 else if (t[tar].l == t[tar].r) 34 t[tar].len2 = 0; 35 else if (t[tar].num == 1) 36 t[tar].len2 = t[tar << 1].len1 + t[tar << 1 | 1].len1; 37 else t[tar].len2 = t[tar << 1].len2 + t[tar << 1 | 1].len2; 38 } 39 40 void build(int l, int r, int tar) 41 { 42 t[tar].l = l, t[tar].r = r, t[tar].len1 = t[tar].len2 = 0, t[tar].num = 0; 43 if (l == r) return; 44 int mid = (l + r) >> 1; 45 build(l, mid, tar << 1), build(mid + 1, r, tar << 1 | 1); 46 } 47 48 void update(int l, int r, int v, int tar) 49 { 50 //cout << tar << endl; 51 if (t[tar].l == l && t[tar].r == r) 52 { 53 t[tar].num += v; 54 pushup(tar); 55 return; 56 } 57 int mid = (t[tar].l + t[tar].r) >> 1; 58 if (r <= mid) update(l, r, v, tar << 1); 59 else if (l > mid) update(l, r, v, tar << 1 | 1); 60 else update(l, mid, v, tar << 1), update(mid + 1, r, v, tar << 1 | 1); 61 pushup(tar); 62 } 63 64 int main() 65 { 66 int T; cin >> T; 67 int tot; 68 while (T--) 69 { 70 int n; cin >> n; 71 72 tot = 0; 73 for (int i = 1; i <= n; i++) 74 { 75 double x1, y1, x2, y2; 76 scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); 77 e[i * 2 - 1] = edge(x1, x2, y1, 1); 78 e[i * 2] = edge(x1, x2, y2, -1); 79 x[i * 2 - 1] = x1, x[i * 2] = x2; 80 } 81 sort(e + 1, e + 1 + 2 * n); 82 sort(x + 1, x + 1 + 2 * n); 83 tot = unique(x + 1, x + 1 + 2 * n) - x - 1; 84 //cout << tot << endl; 85 build(1, tot - 1, 1); 86 double res = 0; 87 for (int i = 1; i < 2 * n; i++) 88 { 89 int x1 = lower_bound(x + 1, x + 1 + tot, e[i].x1) - x; 90 int x2 = lower_bound(x + 1, x + 1 + tot, e[i].x2) - x; 91 //cout << x1 << " " << x2 << endl; 92 update(x1, x2 - 1, e[i].flag, 1); 93 res += (e[i + 1].h - e[i].h) * t[1].len2; 94 } 95 printf("%.2f\n", res); 96 } 97 }