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; }
 
  |