BOJ 2185 직사각형의 합집합

https://www.acmicpc.net/problem/2185

2185번: 직사각형의 합집합

 

풀이 쓰기 귀찮아서 shiftpsh 님에게 대신 써달라고 했습니다. 아래는 shiftpsh 님의 글입니다.

 

둘레를 구해야 한다는 점에서 생각해 보면 $x$축과 $y$축을 따로 생각해도 된다는 사실을 알 수 있습니다. 지금부터는 $x$축에 수직인 선분들만에 대해 설명해 보겠습니다.

 

직사각형의 양 끝 선분을 봅시다. 왼쪽 선분을 '선분이 추가되는 이벤트'로, 오른쪽을 '선분이 삭제되는 이벤트'로 생각하고 모든 직사각형들에 대한 이벤트를 왼쪽에서 오른쪽 순서가 되도록 정렬합니다. 이제 정렬된 이벤트들에 대해 생각해 봅시다. 이런 기법을 '스위핑'이라고 합니다.

 

지금 보고 있는 이벤트와 이전 이벤트를 비교해 보도록 합시다. 여기서 한 가지 관찰을 할 수 있는데, (직전 이벤트에서 겹쳐 있는 선분들의 길이의 합)과 (지금 보고 있는 이벤트에서 겹쳐 있는 선분들의 길이의 합)의 차이들을 모아 보면 구하고자 하는 도형의 둘레(중에서 $x$축에 수직인 선분들의 합)가 된다는 것입니다.

 

까지 shiftpsh 님이 써주셨습니다.

 

이제 매 이벤트마다 선분이 어떻게 변하는지 확인한 뒤, 변화값을 답에 더해주면 됩니다. 이는 1차원 배열 하나와 세그먼트 트리를 통해 관리할 수 있습니다. 선분이 추가되는 이벤트에서는 해당 구간의 배열에 1을 더해주고 삭제되는 이벤트에서는 해당 구간의 배열에 -1을 더해줍니다. 전자의 경우 배열의 값이 1이 되면 칸에 새로운 선분이 추가되었다는 뜻이므로 세그먼트 트리에서 해당 인덱스의 값을 1 증가시킵니다. 후자의 경우 배열의 값이 0이 되면 칸에 있던 선분이 사라졌다는 뜻이므로 세그먼트 트리에서 해당 인덱스의 값을 1 감소시킵니다. 이렇게 관리하면 세그먼트 트리에서의 전체 구간의 합이 현재 가지고 있는 선분의 길이가 됩니다.

 

사실 대충 계산해보고 2억이라서 안 돌거 같다고 생각했는데 생각보다 빠르게 돌아서 놀랐습니다. 아직도 시간복잡도는 잘 모르겠습니다.

 

3일 정도 고민하다가 여기저기 답 물어보고 해서 풀었습니다. 짜기 싫어서 버티다가 scpc 끝나고 더는 버틸 핑계가 없어서 짰습니다. 저는 분명 골랜디를 하고 있는데 왜 자꾸 플레 문제를 받게 되는 걸까요? 모를 일입니다. 그치만 풀릴 거 같은 플레들만 받고 있기 때문에 나름 좋은 일일지도 몰라요.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define FF first
#define SS second
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()

using namespace std;

struct node {
  int v;

  node() : v(0) {}
  node(int v) : v(v) {}

  node operator+(const node& rhs) const {
    return node(v + rhs.v);
  }
};

int T, n, visited[20010];
vector<pair<pii, pii>> rec;

node tree[80010];

void update(int x, int s, int e, int i, int v) {
  if (s == e && s == i) {
    tree[x] = node(v);
    return;
  }

  int m = (s + e) / 2;
  if (i <= m) update(x * 2, s, m, i, v);
  else update(x * 2 + 1, m + 1, e, i, v);
  tree[x] = tree[x * 2] + tree[x * 2 + 1];
}

node query(int x, int s, int e, int l, int r) {
  if (r < s || e < l) return node();
  if (l <= s && e <= r) return tree[x];
  int m = (s + e) / 2;
  return query(x * 2, s, m, l, r) + query(x * 2 + 1, m + 1, e, l, r);
}

int solve() {
  for (int i = 0; i <= 20000; i++) update(1, 0, 20000, i, 0);
  memset(visited, 0, sizeof(visited));

  vector<pair<int, pair<int, pii>>> line;
  for (auto [p1, p2] : rec) {
    auto [a, b] = p1;
    auto [c, d] = p2;
    line.push_back({ a, {0, {b, d}} });
    line.push_back({ c, {1, {b, d}} });
  }
  sort(all(line));

  int ret = 0;
  int prev = 0;

  for (int k = 0; k < 2 * n; k++) {
    auto [x, p] = line[k];
    auto [op, pp] = p;
    auto [s, e] = pp;

    if (op == 0) {
      for (int i = s; i < e; i++) {
        visited[i]++;
        if(visited[i] == 1) update(1, 0, 20000, i, 1);
      }
    }
    else {
      for (int i = s; i < e; i++) {
        visited[i]--;
        if (visited[i] == 0) update(1, 0, 20000, i, 0);
      }
    }

    int cur = query(1, 0, 20000, 0, 20000).v;
    ret += abs(prev - cur);
    prev = cur;
  }

  return ret;
}

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n;

    rec.resize(n);
    for (int i = 0; i < n; i++) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;

      a += 10000;
      b += 10000;
      c += 10000;
      d += 10000;

      if (a > c) swap(a, c);
      if (b > d) swap(b, d);

      rec[i] = { {a, b}, {c, d} };
    }

    int ans = solve();
    for (int i = 0; i < n; i++) {
      swap(rec[i].FF.FF, rec[i].FF.SS);
      swap(rec[i].SS.FF, rec[i].SS.SS);
    }
    ans += solve();

    cout << ans << endl;
  }

  return 0;
}