BOJ 5826 Figure Eight

다음과 같은 브루트포스를 구상할 수 있습니다.

• 두 직사각형이 공유하는 가로줄의 번호 $m$을 고릅니다.
• 가능한 왼쪽과 오른쪽 세로줄 번호의 쌍 $(l, r)$에 대해, 왼쪽 변이 세로줄 $l$ 위에 있고 오른쪽 변이 세로줄 $r$ 위에 있는 위쪽 직사각형과 아래쪽 직사각형의 최대 면적을 각각 구합니다.
• 위쪽 직사각형들에 대해서 구간 DP를 하여 $[l, r]$에 들어오는 모든 위쪽 직사각형 중 최대 면적을 구하고, 아래쪽 직사각형의 면적을 곱하여 아래쪽 직사각형의 가로 구간이 $[l, r]$일 때의 최대 점수를 구합니다.

세 번째 과정의 시간 복잡도는 $\mathcal{O}(n^3)$입니다. 두 번째 과정도 이 시간 복잡도에 맞추고 싶은데, 어떤 방향으로 스위핑을 하더라도 $\mathcal{O}(n^3 \log n)$보다 빠르게 하기 어려워 보입니다.

여기서는 비트셋을 사용할 수 있습니다. $l$을 고정하고 $r$을 오른쪽으로 움직이는 스위핑을 한다고 하면, 다음과 같이 할 수 있습니다.

• 각 세로줄 $i$에 대해, $i$번째 세로줄에서 .인 가로줄들의 번호의 위치가 1인 비트셋 $B_i$를 전처리해 둡니다.
• 또한, 현재 가로줄 $m$에 대해, 각 세로줄 $i$에서 $m$번째 가로줄을 포함하는 연속한 .의 영역이 1인 비트셋 $C_i$를 만들어 둡니다.
• 먼저 $l$번째 세로줄에서, $C_l$을 가져오고, $B_{l+1}$을 AND합니다.
• $r$을 $l+2$부터 시작하여 $m$번째 가로줄에서 *를 만나거나 줄 끝에 닿을 때까지 다음을 반복합니다.
  • $B_{r}$을 AND하여 유지합니다. 현재 비트셋은 $l$부터 $r$까지를 완전히 이을 수 있는 가로줄들의 집합입니다.
  • 이 집합에 $C_{r}$을 AND한 결과의 최하위 비트와 최상위 비트의 위치를 확인합니다. 최하위 비트의 위치가 $m$보다 작으면, 위쪽 직사각형의 최대 면적을 얻을 수 있습니다. 마찬가지로 최상위 비트의 위치가 $m$보다 크면, 아래쪽 직사각형의 최대 면적을 얻을 수 있습니다.