BOJ 15977 조화로운 행렬

$M = 2$인 경우는 LIS 기본 문제가 됩니다.

$M = 3$인 경우, 세그먼트 트리 기반 LIS를 응용해볼 수 있습니다. 먼저 두 번째와 세 번째 줄을 첫 번째 줄 기준으로 정렬하고, 각각 좌표 압축을 합니다. 그러면 2D 최댓값 세그먼트 트리를 이용하여 다음과 같은 풀이를 생각해볼 수 있습니다.

• 첫 번째 좌표부터 시작하여 순서대로 다음과 같은 동작을 반복합니다.
  • 현재 좌표가 $(x, y)$일 때, $x$좌표도 작고 $y$좌표도 작은 직사각형 영역 내에서 최댓값을 구합니다. 이 값을 $l$이라고 합시다.
  • 현재 좌표를 추가하면, 현재 좌표로 끝나는 삼중 LIS의 길이는 $l + 1$이 됩니다. 이 값을 $(x, y)$의 위치에 저장합니다.

$N$이 20만이므로 이러한 2D 세그먼트 트리를 그대로 만들 수는 없고, 다이나믹 세그먼트 트리 (또는 다이나믹 펜윅 트리)를 이용할 수 있습니다. 이대로 구현하면 시간과 메모리 모두 다소 아슬아슬하게 통과합니다.

다른 풀이도 있지만, 자세한 내용은 모릅니다.