扫描线

 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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int INF  =  1e9;
const i64 INFL = 1e18;
int qread(){
    int w = 1, c, ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}
const int MAXN = 1e5 + 3;
int X1[MAXN], Y1[MAXN];
int X2[MAXN], Y2[MAXN];
int n, h, H[MAXN * 2];
namespace Seg{
    #define lc(t) (t << 1)
    #define rc(t) (t << 1 | 1)
    const int SIZ = 8e5 + 3;
    int T[SIZ], S[SIZ], L[SIZ];
    void pushup(int t, int a, int b){
        S[t] = 0;
        if(a != b){
            S[t] = S[lc(t)] + S[rc(t)];
            L[t] = L[lc(t)] + L[rc(t)];
        }
        if(T[t]) S[t] = L[t];
    }
    void modify(int t, int a, int b, int l, int r, int w){
        if(l <= a && b <= r){
            T[t] += w, pushup(t, a, b);
        } else {
            int c = a + b >> 1;
            if(l <= c) modify(lc(t), a, c, l, r, w);
            if(r >  c) modify(rc(t), c + 1, b, l, r, w);
            pushup(t, a, b);
        }
    }
    void build(int t, int a, int b){
        if(a == b){
            L[t] = H[a] - H[a - 1];
        } else {
            int c = a + b >> 1;
            build(lc(t), a, c);
            build(rc(t), c + 1, b);
            pushup(t, a, b);
        }
    }
    int query(int t){
        return S[t];
    }
}
tuple <int, int, int> P[MAXN];
tuple <int, int, int> Q[MAXN];
int main(){
    n = qread();
    for(int i = 1;i <= n;++ i){
        X1[i] = qread(), Y1[i] = qread();
        X2[i] = qread(), Y2[i] = qread();
        if(X1[i] > X2[i]) swap(X1[i], X2[i]);
        if(Y1[i] > Y2[i]) swap(Y1[i], Y2[i]);
        H[++ h] = Y1[i];
        H[++ h] = Y2[i];
        P[i] = make_tuple(X1[i], Y1[i], Y2[i]);
        Q[i] = make_tuple(X2[i], Y1[i], Y2[i]);
    }
    sort(H + 1, H + 1 + h);
    sort(P + 1, P + 1 + n);
    sort(Q + 1, Q + 1 + n);
    int o = unique(H + 1, H + 1 + h) - H - 1;
    Seg :: build(1, 1, o);
    i64 ans = 0, last = -1;
    int p = 1, q = 1;
    while(p <= n || q <= n){
        int x = INF;
        if(p <= n) x = min(x, get<0>(P[p]));
        if(q <= n) x = min(x, get<0>(Q[q]));
        if(last != -1){
            ans += 1ll * Seg :: query(1) * (x - last);
        }
        last = x;
        while(q <= n && get<0>(Q[q]) == x){
            auto [x, l, r] = Q[q]; ++ q;
            l = lower_bound(H + 1, H + 1 + o, l) - H + 1;
            r = lower_bound(H + 1, H + 1 + o, r) - H;
            Seg :: modify(1, 1, o, l, r, 1);
        }
        while(p <= n && get<0>(P[p]) == x){
            auto [x, l, r] = P[p]; ++ p;
            l = lower_bound(H + 1, H + 1 + o, l) - H + 1;
            r = lower_bound(H + 1, H + 1 + o, r) - H;
            Seg :: modify(1, 1, o, l, r, -1);
        }
    }
    printf("%lld\n", ans);
    return 0;
}