扫描线

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 #define ls rt << 1
 4 #define rs rt << 1 | 1
 5 using namespace std;
 6 ll read() {
 7     ll re = 0, f = 1;
 8     char ch = getchar();
 9     while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -f; ch = getchar();}
10     while (‘0‘ <= ch && ch <= ‘9‘) {re = re * 10 + ch - ‘0‘; ch = getchar();}
11     return re * f;
12 }
13 const int N = 1e5 + 5;
14 int n, xl, yl, xr, yr;
15 struct _line {
16     int l, r, h, f;
17 }line[N << 1];
18 bool cmp(_line a, _line b) {
19     return a.h < b.h;
20 }
21 int tag[N << 3], x[N << 3];
22 ll ans, len[N << 3];
23 void push_up(int rt, int l, int r) {
24     len[rt] = tag[rt] ? len[rt] : (l == r ? 0 : len[ls] + len[rs]);
25     //若不是0，说明被覆盖过了，就不变
26     //向上跟新的时候，如果tag[x]是0，说明还没有覆盖过，
27     //直接向上合并，其中最下方的单点没有长度，所以是0
28 }
29 void change(int rt, int l, int r, int L, int R, int d) {
30     if (L <= l && r <= R) {
31         len[rt] = (tag[rt] += d) ? x[r + 1] - x[l] : 0;
32         //若该节点修改后标记不为0，说明被覆盖过，要重新计算边并集长度
33         //若为0，则通过push_up进行直接合并len[ls] + len[rs]
34         push_up(rt, l, r);
35         return;
36     }
37     int mid = (l + r) / 2;
38     if (L <= mid) {
39         change(ls, l, mid, L, R, d);
40     }
41     if (R > mid) {
42         change(rs, mid + 1, r, L, R, d);
43     }
44     push_up(rt, l, r);
45 }
46 int main () {
47     n = read();
48     for (int i = 1; i <= n; i++) {
49         xl = read();
50         yl = read();
51         xr = read();
52         yr = read();
53         x[(i << 1) - 1] = xl;
54         x[i << 1] = xr;
55         line[(i << 1) - 1] = _line{xl, xr, yl, 1};//四元组表示一条边，1表示下边
56         line[i << 1] = _line{xl, xr, yr, -1};//-1表示上边
57     }
58     sort(x + 1, x + 1 + 2 * n);//排序x轴方便离散化
59     sort(line + 1, line + 1 + 2 * n, cmp);//按y排序
60     int m = unique(x + 1, x + 1 + 2 * n) - x - 2;
61     for (int i = 1; i <= 2 * n; i++) {
62         int xL = lower_bound(x + 1, x + 1 + m, line[i].l) - x;
63         int xR = lower_bound(x + 1, x + 1 + m, line[i].r) - x - 1;//-1 是因为防止出现一个没有长度的点代表区间的情况
64                                                         //所以区间[l,r]用[l,r+1]表示，那么修改的时候就修改[l,r-1]
65         ans += len[1] * (line[i].h - line[i - 1].h);//len[1]是我们关心的答案，而且每次都被更新
66         change(1, 1, m, xL, xR, line[i].f);//修改
67     }
68     printf("%lld\n", ans);
69     return 0;
70 }