화성 지도

Problem link: https://www.acmicpc.net/problem/3392

별거 없다고 생각하고 잡은 문제치고 꽤나 고전했다.

일단 sweeping + segment tree를 사용해서 풀 수 있는 문제인데, segment tree 부분이 일반적으로 널리 퍼져있는 lazy propagation 구현 형태로는 커버하기 어려운 부분이 있다.

sweeping 아이디어 먼저 설명하면, 일단 모든 직사각형을 직사각형을 이루는 두 개의 세로선 형태로 저장한다.

왼쪽 세로선을 opening edge, 오른쪽 세로선을 closing edge라고 불러보자.

x좌표를 1씩 늘려가며 sweeping하면서 opening edge가 등장하면 해당 사각형이 차지하는 y좌표 구간을 1씩 더해준다.

반대로, closing edge가 등장하면 해당 사각형이 차지하는 y좌표 구간을 1씩 빼준다.

결국 매 x좌표마다 전체 y구간(1~30000)에 대해 1 이상인 원소수를 세는 쿼리를 날려주면 가로 길이가 1인 단위 직사각형 넓이를 구할 수 있다.

sweeping 아이디어는 매우 간결한데, 문제는 segment tree이다.

이 문제에서 구간에 대한 업데이트는 더하기로 이뤄지는데 반해, 쿼리는 1 이상인 원소 수로 주어진다.

즉, segment tree의 각 노드 값을 합으로 저장해야 할지, 아니면 구간 내 1 이상의 원소 수로 저장해야할지 난처해진다.

여기서 사용하는 방법은 각 노드를 아래 2가지 값을 갖도록 표현하는 것이다.

• length_[i]: i를 루트로 하는 노드가 표현하는 구간 내에 1 이상의 원소의 수

• change_[i]: i를 루트로 하는 노드가 표현하는 구간에 가해졌던 변화의 총합
  (단, 정확히 이 구간 전체에 가해진 경우만을 표현한다. 이 구간 중 일부에 가해진 경우는 표현하지 않음)

요렇게 정의해준 뒤에 change_를 업데이트하는 segment tree 로직을 구현하고 그 뒤에 이를 사용하는 length_ 업데이트 로직을 추가해주면 된다.

자세한 부분은 코드를 보도록하자.

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

static const int kMaxX = 30001;
static const int kMaxY = 30001;

class Range
{
private:
  int left_;
  int right_;

public:
  Range(void)
  {
  }

  Range(const int left, const int right) : left_(left), right_(right)
  {
  }

  const int left(void) const
  {
    return left_;
  }

  const int right(void) const
  {
    return right_;
  }

  const int length(void) const
  {
    return right_ - left_ + 1;
  }
};

class YTree
{
private:
  int length_[kMaxY * 4];
  int change_[kMaxY * 4];

public:
  YTree(void)
  {
    memset(length_, 0, sizeof(int) * kMaxY * 4);
    memset(change_, 0, sizeof(int) * kMaxY * 4);
  }

  int Query(void)
  {
    return length_[1];
  }

  void Update(const size_t root, const Range root_range, const Range update_range, const int value)
  {
    if (root_range.right() < update_range.left() || update_range.right() < root_range.left())
    {
      return;
    }

    if (update_range.left() <= root_range.left() && root_range.right() <= update_range.right())
    {
      change_[root] += value;
    }
    else
    {
      const Range left_range(root_range.left(), (root_range.left() + root_range.right()) / 2);
      const Range right_range(left_range.right() + 1, root_range.right());

      Update(2 * root, left_range, update_range, value);
      Update(2 * root + 1, right_range, update_range, value);

      // change_[root] += change_[2 * root] + change_[2 * root + 1];
    }

    if (change_[root] != 0)
    {
      length_[root] = root_range.length();
    }
    else
    {
      if (root_range.left() == root_range.right())
      {
        length_[root] = 0;
      }
      else
      {
        length_[root] = length_[2 * root] + length_[2 * root + 1];
      }
    }
  }
};

struct Edge
{
  int y_upper_;
  int y_lower_;
  int is_ending_;

  Edge(const int y_upper, const int y_lower, const int is_ending)
    : y_upper_(y_upper), y_lower_(y_lower), is_ending_(is_ending)
  {
  }
};

YTree y_tree;
vector<vector<Edge> > edges(kMaxX + 1, vector<Edge>());

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  int N;
  cin >> N;

  for (int it = 0; it < N; ++it)
  {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    edges[x1 + 1].emplace_back(y2, y1 + 1, 1);
    edges[x2 + 1].emplace_back(y2, y1 + 1, -1);
  }

  int total = 0;
  for (int xpos = 1; xpos < kMaxX; ++xpos)
  {
    for (const auto& edge : edges[xpos])
    {
      y_tree.Update(1, { 1, kMaxY }, { edge.y_lower_, edge.y_upper_ }, edge.is_ending_);
    }

    total += y_tree.Query();
  }

  cout << total << "\n";

  return 0;
}