포스터

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

그야말로 닉값한다라는 표현이 걸맞을 정도로 매우까다로운 문제였다.

우선, 좌표압축은 당연히 해야하므로 이후 기술에서 좌표는 이미 압축되어 있다고 가정하도록 하겠다.
(사실 여기서도 깨달음이 있었는데, 단순하게 map을 쓰는 좌표압축은 매우 속도가 느리다는 점을 배웠다)

기본 골격은 x축 방향으로 좌표를 스위핑하면서, 매번의 훑기(스윕)마다 포스터를 늦게 붙은 녀석부터 한장씩 붙여보는 것이다.

이 과정에서 포스터의 일부분이 빈공간에 붙게 된다면, 그 면적만큼 해당 포스터가 보이는 면적을 더해주면 된다.

짜증나는 점은 그래서 대체 빈공간 여부를 어떻게 빠르게 확인할 수 있냐?는 것인데 이때 서로소 집합 자료구조를 이용해준다.

어떤 포스터가 붙게되어서 그 공간이 더 이상 빈 공간이 아니게 되면 해당 공간들을 모두 합집합해준다.

이 때 단순히 합집합만 해주게 되면, 매번의 훑기에서 전체 공간의 높이(최대 5000*2)만큼을 훑어주어야 하므로 TLE가 나게 된다.

따라서, 보다 똑똑하게 훑어주어야 하는데 내가 사용한 방법은 합집합 시 항상 그 집합의 대표 번호(루트)를 이 집합이 끝나는 곳의 y좌표로 설정한 것이다.

이렇게 하면, 한번의 Find 연산에서 빈 공간이 아닌 것으로 확인된 공간을 만나면 바로 다음 빈 공간으로 점프할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdint>
#include <map>

using namespace std;

static const int kMaxX = 5000 * 2;
static const int kMaxY = 5000 * 2;

class Poster
{
public:
  static int i2x[kMaxX];
  static int i2y[kMaxY];

  int ll_x_, ll_y_;
  int ur_x_, ur_y_;

  int ll_x_idx_, ll_y_idx_;
  int ur_x_idx_, ur_y_idx_;

  Poster(const int ll_x, const int ll_y, const int ur_x, const int ur_y)
    : ll_x_(ll_x), ll_y_(ll_y), ur_x_(ur_x), ur_y_(ur_y)
  {
  }
};

int Poster::i2x[kMaxX];
int Poster::i2y[kMaxY];

class DisjointSet
{
private:
  int parents_[kMaxY];
  bool is_set_[kMaxY];

public:
  void Initialize(void)
  {
    for (int it = 0; it < kMaxY; ++it)
    {
      parents_[it] = it;
      is_set_[it] = false;
    }
  }

  int Find(const int y)
  {
    if (parents_[y] == y)
    {
      return y;
    }

    return (parents_[y] = Find(parents_[y]));
  }

  void Union(const int lower, const int upper)
  {
    is_set_[lower] = true;
    is_set_[upper] = true;

    int lower_parents = Find(lower);
    int upper_parents = Find(upper);

    parents_[min(lower_parents, upper_parents)] = max(lower_parents, upper_parents);
  }

  bool IsSet(const int y)
  {
    return is_set_[y];
  }
};

void Codec(vector<Poster>& posters)
{
  map<int, int> x_enc;
  map<int, int> y_enc;

  for (const auto& poster : posters)
  {
    x_enc[poster.ll_x_] = 0;
    x_enc[poster.ur_x_] = 0;
    y_enc[poster.ll_y_] = 0;
    y_enc[poster.ur_y_] = 0;
  }

  int idx;

  idx = 0;
  for (auto& x : x_enc)
  {
    x.second = idx;
    Poster::i2x[idx] = x.first;
    ++idx;
  }

  idx = 0;
  for (auto& y : y_enc)
  {
    y.second = idx;
    Poster::i2y[idx] = y.first;
    ++idx;
  }

  for (auto& poster : posters)
  {
    poster.ll_x_idx_ = x_enc[poster.ll_x_];
    poster.ll_y_idx_ = y_enc[poster.ll_y_];
    poster.ur_x_idx_ = x_enc[poster.ur_x_];
    poster.ur_y_idx_ = y_enc[poster.ur_y_];
  }
}

void Solve(vector<Poster>& posters)
{
  vector<uint64_t> areas(posters.size(), 0);

  DisjointSet disjoint_set;

  for (int x_idx = 0; x_idx < kMaxX; ++x_idx)
  {
    disjoint_set.Initialize();

    for (int it = posters.size() - 1; it >= 0; --it)
    {
      if (posters[it].ll_x_idx_ <= x_idx && x_idx < posters[it].ur_x_idx_)
      {
        int y_idx = posters[it].ll_y_idx_;

        while (y_idx < posters[it].ur_y_idx_)
        {
          if (!disjoint_set.IsSet(y_idx))
          {
            areas[it] += static_cast<int64_t>(Poster::i2x[x_idx + 1] - Poster::i2x[x_idx]) *
                         (Poster::i2y[y_idx + 1] - Poster::i2y[y_idx]);
            disjoint_set.Union(posters[it].ll_y_idx_, y_idx++);
          }
          else
          {
            y_idx = disjoint_set.Find(y_idx) + 1;
          }
        }
      }
    }
  }

  for (const auto& area : areas)
  {
    cout << area << "\n";
  }
}

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

  // Read input
  int N;
  cin >> N;

  vector<Poster> posters;
  for (int it = 0; it < N; ++it)
  {
    int ll_x, ll_y, ur_x, ur_y;
    cin >> ll_x >> ll_y >> ur_x >> ur_y;
    posters.emplace_back(ll_x, ll_y, ur_x, ur_y);
  }

  Codec(posters);

  Solve(posters);

  return 0;
}