fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Segment {
  5.     long long l, r;
  6.     long long w;      // 覆盖次数
  7.     long long w1;     // 奇数次覆盖长度
  8.     long long w2;     // 偶数次覆盖长度
  9.     long long len;    // 区间长度
  10. };
  11.  
  12. struct Line {
  13.     long long l, r;
  14.     long long y;
  15.     long long v;      // +1 开始，-1 结束
  16. };
  17.  
  18. class SegmentTree {
  19. private:
  20.     vector<Segment> tree;
  21.     vector<long long> p;  // 离散化数组
  22.  
  23.     void build(long long u, long long l, long long r) {
  24.         tree[u].l = l;
  25.         tree[u].r = r;
  26.         tree[u].len = p[r + 1] - p[l];  // 维护区间[l, r+1]
  27.         if (l == r) return;
  28.  
  29.         long long mid = (l + r) / 2;
  30.         build(u * 2, l, mid);
  31.         build(u * 2 + 1, mid + 1, r);
  32.     }
  33.  
  34. public:
  35.     SegmentTree(long long n, const vector<long long>& points) : p(points) {
  36.         tree.resize(4 * n);
  37.         build(1, 1, n);
  38.     }
  39.  
  40.     void update(long long u, long long l, long long r, long long k) {
  41.         if (tree[u].l > r || tree[u].r < l) return;
  42.  
  43.         if (tree[u].l >= l && tree[u].r <= r) {
  44.             tree[u].w += k;  // 更新覆盖次数
  45.         } else {
  46.             update(u * 2, l, r, k);
  47.             update(u * 2 + 1, l, r, k);
  48.         }
  49.  
  50.         if (tree[u].l == tree[u].r) {  // 叶节点
  51.             if (!tree[u].w) {
  52.                 tree[u].w1 = tree[u].w2 = 0;
  53.             } else if (tree[u].w & 1) {
  54.                 tree[u].w1 = tree[u].len;
  55.                 tree[u].w2 = 0;
  56.             } else {
  57.                 tree[u].w1 = 0;
  58.                 tree[u].w2 = tree[u].len;
  59.             }
  60.         } else {  // 非叶节点
  61.             if (!tree[u].w) {
  62.                 tree[u].w1 = tree[u * 2].w1 + tree[u * 2 + 1].w1;
  63.                 tree[u].w2 = tree[u * 2].w2 + tree[u * 2 + 1].w2;
  64.             } else if (tree[u].w & 1) {
  65.                 tree[u].w2 = tree[u * 2].w1 + tree[u * 2 + 1].w1;
  66.                 tree[u].w1 = tree[u].len - tree[u].w2;
  67.             } else {
  68.                 tree[u].w1 = tree[u * 2].w1 + tree[u * 2 + 1].w1;
  69.                 tree[u].w2 = tree[u].len - tree[u].w1;
  70.             }
  71.         }
  72.     }
  73.  
  74.     long long getOddCovered() const { return tree[1].w1; }
  75.     long long getEvenCovered() const { return tree[1].w2; }
  76. };
  77.  
  78. int main() {
  79.     long long n;
  80.     cin >> n;
  81.  
  82.     vector<Line> lines;
  83.     vector<long long> points;
  84.  
  85.     for (long long i = 0; i < n; ++i) {
  86.         long long l, d, r, u;
  87.         cin >> l >> d >> r >> u;
  88.  
  89.         lines.push_back({l, r, d, 1});
  90.         lines.push_back({l, r, u, -1});
  91.         points.push_back(l);
  92.         points.push_back(r);
  93.     }
  94.  
  95.     // 排序并去重
  96.     sort(lines.begin(), lines.end(), [](const Line& a, const Line& b) {
  97.         return a.y < b.y;
  98.     });
  99.  
  100.     sort(points.begin(), points.end());
  101.     points.erase(unique(points.begin(), points.end()), points.end());
  102.  
  103.     long long cnt = points.size() - 1;
  104.     SegmentTree st(cnt, points);
  105.  
  106.     long long ans1 = 0, ans2 = 0;
  107.  
  108.     for (size_t i = 0; i < lines.size(); ++i) {
  109.         if (i > 0) {
  110.             long long dy = lines[i].y - lines[i - 1].y;
  111.             ans1 += static_cast<long long>(st.getOddCovered()) * dy;
  112.             ans2 += static_cast<long long>(st.getEvenCovered()) * dy;
  113.         }
  114.  
  115.         long long l = lower_bound(points.begin(), points.end(), lines[i].l) - points.begin() + 1;
  116.         long long r = lower_bound(points.begin(), points.end(), lines[i].r) - points.begin() + 1;
  117.         st.update(1, l, r - 1, lines[i].v); 
  118.     }
  119.  
  120.     printf("%lld\n%lld\n", ans1, ans2);
  121.     return 0;
  122. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
3
1 1 3 3
2 2 4 4
3 3 5 5
stdout
copy 
158
2
https://ideone.com/Xv0G2r
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!