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 98 99 100 101 102 103 104 105 106
|
#include <bits/stdc++.h> #include <tr1/unordered_map>
inline char read() { static const int IN_LEN = 10000000; static char buf[IN_LEN], *s, *t; if (s == t) { t = (s = buf) + fread(buf, 1, IN_LEN, stdin); if (s == t) return -1; } return *s++; }
template<class T> inline void read(T &x) { static char c; static bool iosig; for (c = read(), iosig = false; !isdigit(c); c = read()) { if (c == -1) return; if (c == '-') iosig = true; } for (x = 0; isdigit(c); c = read()) x = (x + (x << 2) << 1) + (c ^ '0'); if (iosig) x = -x; }
namespace SegmentTree {
const int MAXN = 200010;
#define long long long
int x[MAXN], size; std::tr1::unordered_map<int, int> pos;
struct Segment { int x1, x2, h; int type; Segment() {} Segment(int x1, int x2, int h, int type): x1(x1), x2(x2), h(h), type(type) {} inline friend bool operator<(const Segment &a, const Segment &b) { return a.h < b.h; } } a[MAXN];
struct Node { int cnt, sum, len; } d[MAXN << 2];
int M;
inline void build(const int n) { for (M = 1; M < n + 2; M <<= 1); for (register int i = 1; i <= n; i++) d[i + M].len = x[i] - x[i - 1]; for (register int i = M - 1; i; i--) d[i].len = d[i << 1].len + d[i << 1 | 1].len; }
inline void pushUp(int k) { d[k].sum = d[k].cnt ? d[k].len : (k >= M ? 0 : d[k << 1].sum + d[k << 1 | 1].sum); }
inline void update(int k) { for (; k; k >>= 1) pushUp(k); }
inline void insert(int s, int t, int v) { register int l = 0, r = 0; for (l = s = s + M - 1, r = t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) { (~s & 1) ? (d[s ^ 1].cnt += v, pushUp(s ^ 1), 0) : 0; (t & 1) ? (d[t ^ 1].cnt += v, pushUp(t ^ 1), 0) : 0; } for (; l; l >>= 1) pushUp(l); for (; r; r >>= 1) pushUp(r); }
inline void solve() { register int n; read(n); for (register int i = 1, x1, x2, y1, y2; i <= 2 * n; i += 2) { read(x1), read(y1), read(x2), read(y2); x[i] = x1, x[i + 1] = x2; a[i] = Segment(x1, x2, y1, 1); a[i + 1] = Segment(x1, x2, y2, -1); } std::sort(a + 1, a + 2 * n + 1); std::sort(x + 1, x + 2 * n + 1); size = std::unique(x + 1, x + 2 * n + 1) - (x + 1); for (register int i = 1; i <= size; i++) pos[x[i]] = i; build(size); long ans = 0; a[0].h = a[1].h; for (register int i = 1; i <= 2 * n; i++) { ans += ((long)a[i].h - a[i - 1].h) * d[1].sum; insert(pos[a[i].x1] + 1, pos[a[i].x2], a[i].type); } std::cout << ans; } }
int main() { SegmentTree::solve(); return 0; }
|