직사각형 타일링

직사각형은 첫 번째 행만 덮는 것, 두 번째 행만 덮는 것, 두 행을 모두 덮는 것의 세 종류이다.

두 행을 모두 덮는 직사각형들을 몇 개 선택했다고 하자. 이들은 왼쪽부터 서로 겹치지 않게 놓여야 한다. 연속한 두 전행 직사각형 사이에서는 첫 번째 행과 두 번째 행의 한 행 직사각형들을 서로 독립적으로 최대로 선택할 수 있다.

한 행에서 시작점 $s$ 이후 선택 가능한 직사각형 중 오른쪽 끝이 가장 작은 것을 고르는 표준 구간 스케줄링 그리디를 생각하자. 그 다음 시작점은 방금 고른 오른쪽 끝이 된다. 각 좌표 $x$의 부모를 이 next$(x)$의 오른쪽 끝으로 두면 그리디 선택 과정이 트리의 조상 경로가 된다. 따라서 스위프가 한 행 직사각형의 오른쪽 끝 $e$를 지날 때, $e$의 서브트리에 속하는 모든 시작점의 값에 $1$을 더하면 된다.

가능한 시작점은 $0$과 전행 직사각형들의 오른쪽 끝이다. 두 행에서 만든 트리를 각각 DFS하여 한 시작점 $s$를 두 DFS 번호의 점 $(p_1(s),p_2(s))$로 나타낸다. 첫 번째 행의 서브트리 증가는 점들의 세로 띠 범위 덧셈, 두 번째 행의 증가는 가로 띠 범위 덧셈이 된다.

이 정적 점들을 2차원 KD Tree에 저장하여 각 노드의 경계 직사각형, 최댓값, lazy 증가량을 관리한다. 세로/가로 띠 업데이트는 $O(\sqrt K)$에 처리할 수 있다. 열 좌표를 왼쪽에서 오른쪽으로 스위프하며, 전행 직사각형의 왼쪽 끝에서는 현재 전체 최댓값에 $1$을 더해 그 직사각형을 마지막으로 고르는 DP 값을 구한다. 한 행 직사각형의 오른쪽 끝 업데이트를 처리한 뒤, 전행 직사각형의 오른쪽 끝 좌표를 새 시작점으로 활성화한다.

전체 시간 복잡도는 $O(K\sqrt K+K\log K)$이다. Solution written by GPT5.6