1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 1e5 + 5;
const int I = 1e9 + 2;
int n;
int b[N * 2], xs[N * 2];
int stot;
struct Scanning_Line {
int x, y, _y, val;
Scanning_Line(int x = 0, int y = 0, int _y = 0, int val = 0) : x(x), y(y), _y(_y), val(val) {}
bool operator< (const Scanning_Line &a) const {
return x < a.x;
}
} S[N * 2];
struct Node {
int mn, mncnt;
Node(int mn = 0, int mncnt = 0) : mn(mn), mncnt(mncnt) {}
friend Node operator+ (const Node a, const Node b) {
Node c;
c.mn = min(a.mn, b.mn);
if (a.mn == c.mn) c.mncnt += a.mncnt;
if (b.mn == c.mn) c.mncnt += b.mncnt;
return c;
}
} T[N * 70];
int tag[N * 70];
int ls[N * 70], rs[N * 70];
int tot = 1;
inline void maketag(int o, int x) {
tag[o] += x;
T[o].mn += x;
}
inline void pushdown(int o) {
if (!tag[o]) return;
maketag(ls[o], tag[o]);
maketag(rs[o], tag[o]);
tag[o] = 0;
}
void update(int o, int l, int r, int x, int y, int k) {
if (x <= l && r <= y) return maketag(o, k);
int mid = l + r >> 1;
if (!ls[o]) {
ls[o] = ++tot; rs[o] = ++tot;
T[ls[o]] = Node(T[o].mn, mid - l + 1);
T[rs[o]] = Node(T[o].mn, r - mid);
tag[o] = 0;
} else pushdown(o);
if (x <= mid) update(ls[o], l, mid, x, y, k);
if (mid < y) update(rs[o], mid + 1, r, x, y, k);
T[o] = T[ls[o]] + T[rs[o]];
}
int main(void) {
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
int x, y, _x, _y; cin >> x >> y >> _x >> _y;
--_x, --_y;
S[++stot] = Scanning_Line(x, y, _y, 1);
S[++stot] = Scanning_Line(_x + 1, y, _y, -1);
}
sort(S + 1, S + stot + 1);
for (int i = 1; i <= stot; ++i) xs[i] = S[i].x;
int m = unique(xs + 1, xs + stot + 1) - (xs + 1);
i64 ans = 0;
T[1].mncnt = I + 1;
for (int i = 1, j = 0; i <= m; ++i) {
if (i > 1) ans += 1ll * (xs[i] - xs[i - 1]) * (I + 1 - T[1].mncnt);
while (j < stot && S[j + 1].x == xs[i]) ++j, update(1, 0, I, S[j].y, S[j]._y, S[j].val);
}
cout << ans << "\n";
return 0;
}
|