test/ds/lzsgt4sl.cpp

• View this file on GitHub
• Last update: 2025-10-17 14:01:51+08:00
• Problem: https://judge.yosupo.jp/problem/area_of_union_of_rectangles

Depends on

• src/ds/lzsgt4sl.hpp
• src/misc/read.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/area_of_union_of_rectangles
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define PUSHB push_back
using namespace std;
using ll = long long;

#include "../../src/ds/lzsgt4sl.hpp"
#include "../../src/misc/read.hpp"

struct Line {
  int sign, x, y1, y2;
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read();
  vector<Line> a(2 * n);
  vector<int> dc(2 * n);
  for (int i = 0; i < 2 * n; i += 2) {
    int x1 = read(), y1 = read(), x2 = read(), y2 = read();
    a[i] = {1, x1, y1, y2}, a[i + 1] = {-1, x2, y1, y2};
    dc[i] = y1, dc[i + 1] = y2;
  }
  sort(ALL(dc)), dc.erase(unique(ALL(dc)), dc.end());
  map<int, int> mp;
  int N = dc.size();
  for (int i = 0; i < N; i++) {
    mp[dc[i]] = i;
  }
  sort(ALL(a), [](const Line& lhs, const Line& rhs) { return lhs.x < rhs.x; });
  for (auto& [_, __, y1, y2] : a) {
    y1 = mp[y1], y2 = mp[y2];
  }

  vector<int> init(N - 1);
  for (int i = 0; i < N - 1; i++) {
    init[i] = dc[i + 1] - dc[i];
  }
  SegTree sgt(init);

  ll ans = 0;
  sgt.apply(a[0].y1, a[0].y2, a[0].sign);
  for (int i = 1; i < 2 * n; i++) {
    ans += ll(sgt.sum[1]) * (a[i].x - a[i - 1].x);
    sgt.apply(a[i].y1, a[i].y2, a[i].sign);
  }
  cout << ans << "\n";
  return 0;
}

#line 1 "test/ds/lzsgt4sl.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/area_of_union_of_rectangles
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define PUSHB push_back
using namespace std;
using ll = long long;

#line 1 "src/ds/lzsgt4sl.hpp"
// 针对扫描线特化的线段树, 支持区间覆盖, 撤销覆盖, 查询被覆盖的总长度.
struct SegTree {
  int n, _l, _r, _f;
  const vector<int>& _a;
  vector<int> len, sum, tag;
  SegTree(const vector<int>& a)
      : n(a.size()), _a(a), len(4 * n), sum(4 * n), tag(4 * n) {
    build(1, 0, n);
  }
  void apply(int l, int r, int f) { _l = l, _r = r, _f = f, apply_(1, 0, n); }

 private:
  void build(int p, int pl, int pr) {
    if (pr - pl == 1) return len[p] = _a[pl], void();
    int ls = p * 2, rs = p * 2 + 1, mid = pl + (pr - pl) / 2;
    build(ls, pl, mid), build(rs, mid, pr);
    len[p] = len[ls] + len[rs];
  }
  void apply_(int p, int pl, int pr) {
    if (_r <= pl || pr <= _l) return;
    int ls = p * 2, rs = p * 2 + 1, mid = pl + (pr - pl) / 2;
    if (_l <= pl && pr <= _r) {
      sum[p] = (tag[p] += _f) ? len[p] : (pr - pl == 1 ? 0 : sum[ls] + sum[rs]);
      return;
    }
    apply_(ls, pl, mid), apply_(rs, mid, pr);
    sum[p] = tag[p] ? len[p] : sum[ls] + sum[rs];
  }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 10 "test/ds/lzsgt4sl.cpp"

struct Line {
  int sign, x, y1, y2;
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read();
  vector<Line> a(2 * n);
  vector<int> dc(2 * n);
  for (int i = 0; i < 2 * n; i += 2) {
    int x1 = read(), y1 = read(), x2 = read(), y2 = read();
    a[i] = {1, x1, y1, y2}, a[i + 1] = {-1, x2, y1, y2};
    dc[i] = y1, dc[i + 1] = y2;
  }
  sort(ALL(dc)), dc.erase(unique(ALL(dc)), dc.end());
  map<int, int> mp;
  int N = dc.size();
  for (int i = 0; i < N; i++) {
    mp[dc[i]] = i;
  }
  sort(ALL(a), [](const Line& lhs, const Line& rhs) { return lhs.x < rhs.x; });
  for (auto& [_, __, y1, y2] : a) {
    y1 = mp[y1], y2 = mp[y2];
  }

  vector<int> init(N - 1);
  for (int i = 0; i < N - 1; i++) {
    init[i] = dc[i + 1] - dc[i];
  }
  SegTree sgt(init);

  ll ans = 0;
  sgt.apply(a[0].y1, a[0].y2, a[0].sign);
  for (int i = 1; i < 2 * n; i++) {
    ans += ll(sgt.sum[1]) * (a[i].x - a[i - 1].x);
    sgt.apply(a[i].y1, a[i].y2, a[i].sign);
  }
  cout << ans << "\n";
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	edge_bound_00	AC	1373 ms	120 MB
g++	edge_bound_01	AC	1389 ms	120 MB
g++	edge_bound_02	AC	1339 ms	121 MB
g++	edge_bound_03	AC	1379 ms	120 MB
g++	edge_bound_04	AC	1352 ms	120 MB
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	1824 ms	120 MB
g++	max_random_01	AC	1907 ms	120 MB
g++	max_random_02	AC	1850 ms	121 MB
g++	max_random_03	AC	1865 ms	121 MB
g++	max_random_04	AC	1858 ms	120 MB
g++	random_00	AC	1313 ms	95 MB
g++	random_01	AC	1675 ms	112 MB
g++	random_02	AC	118 ms	16 MB
g++	random_03	AC	1440 ms	104 MB
g++	random_04	AC	845 ms	68 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB

Back to top page