최대 증가 직사각형 집합

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

개인적으로 보기에는 화성지도와 유사한 문제인데, 특정한 축(나는 x축을 선택했음)을 기준으로 sweeping하면서 다른 축에 대한 구간 쿼리(나는 y축)를 진행하는 방식으로 문제를 풀 수 있다.

구현 자체로는 크게 어려운 점이 없지만, 알고리즘이 꽤 여러 단계의 사고를 요하기 때문에 아래에 조금 상세히 기술해보도록 하겠다.

1. DP 솔루션을 떠올려본다면?

우선, 이 문제를 푸는 DP 솔루션을 떠올려보자.

DP[i] := i번 사각형에서 끝나는 최대 증가 직사각형 집합의 길이

위와 같이 정의하면, 아래와 같이 아주 쉽게 점화식을 세워줄 수 있다.

DP[i]=max(D[j]) + 1(단, j번 사각형이 i번 사각형 전에 위치할 수 있어야 함)

일단 자세한 내용은 차치하고 위의 점화식을 뜯어보면, 아래와 같은 2가지 생각이 들 것이다.

• 음...max가 들어가니까 뭔가 log 복잡도 알고리즘으로 처리해봄직 하군

• "j번 사각형이 i번 전에 위치할 수 있어야 함" 이라는 조건이 매우 까다롭군...

  • 이 조건을 formal하게 적으면 아래와 같다.
    • square[j].ur_x < square[i].ll_x && square[j].ur_y < square[i].ll_y

2. segment tree + sweeping 솔루션을 적용해본다면?

1절에서 떠올린 2가지의 생각은 segment tree와 sweeping을 도입하면 우아하게 해결해볼 수 있다.

일단, 아래의 쿼리를 지원하는 segment tree를 가지고 있다고 가정해보자.

MaxQuery(s, e):= s <= square[x].ur_y <= e인 사각형 x들로 만들 수 있는 최대 증가 직사각형 집합의 길이

이제, x축을 따라서 평면을 sweeping하면서 x == square[i].ll_x인 임의의 i번째 사각형을 만나게 되었다고 하자.

상술하였듯이 i번째 사각형으로 끝나는 최대 증가 직사각형 집합의 길이를 찾기 위해서는 i번째 앞에 올 수 있는 사각형들 중 그 DP 값이 최대 녀석을 찾아야한다.

이 값은 MaxQuery(0, square[i].ll_y - 1)을 통해 구할 수 있는데 왜 그런지를 잘 생각해보자.

square[j].ur_x < square[i].ll_x && square[j].ur_y < square[i].ll_y 조건을 만족하는 사각형이 곧 i번째 사각형 앞에 올 수 있는 사각형인데,

• x축을 기준으로 sweeping을 진행 중이므로 앞선 x 값과 관련된 조건은 자연스럽게 충족된다.
  (square[i].ll_x보다 큰 곳은 아직 보지도 않았음)
• y축을 기준으로는 이미 segment tree를 들고 있으므로 해당 구간에 대해 쉽게 값을 구할 수 있다.

이제 위에 기술한 방법을 바탕으로 i번째 사각형에 대해 DP[i]=X임을 알게되었다고 하자.

이 값 역시 이후에 있을 MaxQuery들을 위해 segment tree에 들어가줘야하고, segment tree의 정의 상 Update(square[i].ur_y, X)로 업데이트 해주면 된다.
(단, X=max(X, MaxQuery(square[i].ur_y, square[i].ur_y)))

하지만, 한가지 주의할 점은 DP[i]=X가 결정된 직후에 바로 이를 업데이트해주면 안된다는 점인데 이는 아래의 반례를 잘 생각해보면 된다.

• DP[i]=X가 결정되자마자 Update(square[i].ur_y, X)로 segment tree를 업데이트 하였다.
• sweeping을 한단계 더 진행하여 이제 x == square[i].ll_x + 1을 보게되었고, i+1번째 사각형을 만나게되었다고 하자.
• 이 지점은 아직 i번째 사각형이 채 끝나지 않은 지점이라고 가정하자.
• 이 때, 이 지점에서 이뤄지는 MaxQuery(0, square[i+1].ur_y - 1)는 자명하게 i번째 사각형의 Update로 인한 영향을 받지 않아야한다.
  (i번째 사각형이 i+1번째 사각형 전에 올 수 없으므로)

상술한 반례는 Update들을 모아두었다가 실제로 해당 업데이트를 유발한 사각형이 끝나는 지점을 sweeping할 때 업데이트들을 일괄로 적용해주는 것이다.

말로 적으니 굉장히 복잡한데, 단순하게 사각형이 끝나는 지점을 키로하는 PQ를 도입하여 쉽게 적용할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

// Class representing rectangle
class Rectangle
{
private:
  int lower_left_xpos_;
  int lower_left_ypos_;
  int upper_right_xpos_;
  int upper_right_ypos_;

public:
  Rectangle(void)
  {
  }
  Rectangle(const int lower_left_xpos, const int lower_left_ypos, const int upper_right_xpos,
            const int upper_right_ypos)
    : lower_left_xpos_(lower_left_xpos)
    , lower_left_ypos_(lower_left_ypos)
    , upper_right_xpos_(upper_right_xpos)
    , upper_right_ypos_(upper_right_ypos)
  {
  }

  const int lower_left_xpos(void) const
  {
    return lower_left_xpos_;
  }
  const int lower_left_ypos(void) const
  {
    return lower_left_ypos_;
  }
  const int upper_right_xpos(void) const
  {
    return upper_right_xpos_;
  }
  const int upper_right_ypos(void) const
  {
    return upper_right_ypos_;
  }
};

// Class representing lazy update
struct LazyUpdate
{
  int xpos_;
  int ypos_;
  int dp_;

  LazyUpdate(const int xpos, const int ypos, const int dp) : xpos_(xpos), ypos_(ypos), dp_(dp)
  {
  }

  bool operator<(const LazyUpdate& rhs) const
  {
    return xpos_ < rhs.xpos_;
  }

  bool operator>(const LazyUpdate& rhs) const
  {
    return xpos_ > rhs.xpos_;
  }
};

// Class representing segment tree supporting max query
class MaxTree
{
private:
  int node_[100001 * 4];

  int Update(const int root, const int left, const int right, const int update_index, const int update_value)
  {
    if (right < update_index || update_index < left)
    {
      return node_[root];
    }

    if (left == right)
    {
      return (node_[root] = update_value);
    }

    int mid = (left + right) / 2;
    int left_tree = Update(2 * root, left, mid, update_index, update_value);
    int right_tree = Update(2 * root + 1, mid + 1, right, update_index, update_value);

    return (node_[root] = max(left_tree, right_tree));
  }

  int Query(const int root, const int left, const int right, const int query_left, const int query_right)
  {
    if (right < query_left || query_right < left)
    {
      return 0;
    }

    if (query_left <= left && right <= query_right)
    {
      return node_[root];
    }

    int mid = (left + right) / 2;
    int left_tree = Query(2 * root, left, mid, query_left, query_right);
    int right_tree = Query(2 * root + 1, mid + 1, right, query_left, query_right);

    return max(left_tree, right_tree);
  }

public:
  MaxTree(void)
  {
    memset(node_, 0, sizeof(int) * 100001 * 4);
  }

  void Update(const int ypos, const int dp)
  {
    Update(1, 1, 100001, ypos + 1, dp);
  }

  int Query(const int left, const int right)
  {
    return Query(1, 1, 100001, left + 1, right + 1);
  }
};

vector<Rectangle> axis[100001];
MaxTree max_tree;

int Solve(void)
{
  priority_queue<LazyUpdate, vector<LazyUpdate>, greater<LazyUpdate> > lazy_update;

  for (int xpos = 0; xpos <= 100000; ++xpos)
  {
    while (!lazy_update.empty() && lazy_update.top().xpos_ < xpos)
    {
      int ypos = lazy_update.top().ypos_;
      int dp = lazy_update.top().dp_;
      lazy_update.pop();

      max_tree.Update(ypos, max(dp, max_tree.Query(ypos, ypos)));
    }

    for (const auto& rect : axis[xpos])
    {
      int len = max_tree.Query(0, rect.lower_left_ypos() - 1) + 1;
      lazy_update.emplace(rect.upper_right_xpos(), rect.upper_right_ypos(), len);
    }
  }

  return max_tree.Query(0, 100000);
}

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

  // Read input
  int N;
  cin >> N;
  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;
    axis[ll_x].emplace_back(ll_x, ll_y, ur_x, ur_y);
  }

  // Solve
  cout << Solve() << "\n";

  return 0;
}