You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
82 lines
1.8 KiB
82 lines
1.8 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
typedef long long LL;
|
|
const int N = 1e6 + 10;
|
|
LL res;
|
|
int n;
|
|
int b[N];
|
|
|
|
// 横版
|
|
struct ScanLine {
|
|
int x1, x2, y, mark;
|
|
const bool operator<(const ScanLine &t) {
|
|
return y < t.y;
|
|
}
|
|
} line[N << 1];
|
|
|
|
struct Node {
|
|
int l, r;
|
|
int len;
|
|
int cnt;
|
|
} tr[N << 2];
|
|
|
|
void pushup(int u) {
|
|
if (tr[u].cnt)
|
|
tr[u].len = b[tr[u].r + 1] - b[tr[u].l];
|
|
else
|
|
tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
|
|
}
|
|
|
|
void build(int u, int l, int r) {
|
|
tr[u].l = l, tr[u].r = r;
|
|
if (l == r) return;
|
|
int mid = (l + r) >> 1;
|
|
build(u << 1, l, mid);
|
|
build(u << 1 | 1, mid + 1, r);
|
|
}
|
|
|
|
void modify(int u, int l, int r, int v) {
|
|
if (l <= tr[u].l && r >= tr[u].r) {
|
|
tr[u].cnt += v;
|
|
pushup(u);
|
|
return;
|
|
}
|
|
|
|
int mid = (tr[u].l + tr[u].r) >> 1;
|
|
if (l <= mid) modify(u << 1, l, r, v);
|
|
if (r > mid) modify(u << 1 | 1, l, r, v);
|
|
|
|
pushup(u);
|
|
}
|
|
|
|
int main() {
|
|
#ifndef ONLINE_JUDGE
|
|
freopen("P5490.in", "r", stdin);
|
|
#endif
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
cin >> n;
|
|
int x1, x2, y1, y2;
|
|
for (int i = 1; i <= n; i++) {
|
|
cin >> x1 >> y1 >> x2 >> y2;
|
|
b[i * 2 - 1] = x1, b[i * 2] = x2;
|
|
line[i * 2 - 1] = {x1, x2, y1, 1};
|
|
line[i * 2] = {x1, x2, y2, -1};
|
|
}
|
|
|
|
n *= 2;
|
|
sort(line + 1, line + n + 1);
|
|
sort(b + 1, b + n + 1);
|
|
int tot = unique(b + 1, b + n + 1) - b - 1;
|
|
build(1, 1, tot - 1);
|
|
|
|
for (int i = 1; i < n; i++) {
|
|
int L = lower_bound(b + 1, b + tot + 1, line[i].x1) - b;
|
|
int R = lower_bound(b + 1, b + tot + 1, line[i].x2) - b;
|
|
modify(1, L, R - 1, line[i].mark);
|
|
res += (LL)tr[1].len * (line[i + 1].y - line[i].y);
|
|
}
|
|
|
|
printf("%lld\n", res);
|
|
return 0;
|
|
} |