BOJ 15977 조화로운 행렬

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

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

• 첫 번째 좌표부터 시작하여 순서대로 다음과 같은 동작을 반복합니다.
  • 현재 좌표가 $(x, y)$일 때, $x$좌표도 작고 $y$좌표도 작은 직사각형 영역 내에서 최댓값을 구합니다. 이 값을 $l$이라고 합시다.
  • 현재 좌표를 추가하면, 현재 좌표로 끝나는 삼중 LIS의 길이는 $l + 1$이 됩니다. 이 값을 $(x, y)$의 위치에 저장합니다.
  • DP 식으로 나타내면, $i$번째 점이 $(x_i, y_i)$일 때, $DP[i] = 1 + \max_{j < i, x_j < x_i, y_j, y_i} DP[j]$입니다.

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

다른 풀이로는 다음과 같은 풀이가 있습니다.

• justiceHui의 풀이: 각 점에서 끝나는 삼중 LIS의 길이가 같은 점들을 하나의 집합으로 묶으면, 이 점들을 $x$ 증가순으로 나열했을 때 $y$는 모두 감소합니다. 따라서 이러한 집합을 $N$개의 트리셋에 넣고, 새로운 점에 대해 “$k$번째 집합에 자신보다 $x$, $y$ 모두 작은 점이 존재하는가?“에 대해 이분 탐색을 하여 그러한 최대 $k$를 구한 다음, 현재 점을 $k+1$번 집합에 넣는 것을 반복하여 풀 수 있습니다.
• koosaga의 풀이: 분할 정복을 하는데, 점이 추가되는 순서 상으로 앞쪽 절반으로 먼저 재귀하고, 앞쪽 절반에서 뒤쪽 절반으로 DP 전파를 한 뒤에 뒤쪽 절반으로 재귀합니다. DP 전파는 나이브로 하면 $N^2$ 시간이 걸리지만, 세그먼트 트리를 사용해 $N \log N$으로 최적화할 수 있습니다.

모든 풀이의 시간 복잡도는 $\mathcal{O}(N \log^2 N)$입니다.