A. Battleship

ProblemA_Eng.pdf

입력으로 주어지는 두 점 $(x1,y1)$ <--> $(x2,y2)$를 잇는 선분이 있다.

(WLOG 편의상 $x1 \le x2 , y1 \le y2$)

입력으로 주어지는 직선은 수직선이나 수평선이다.

따라서 $x = a$ 꼴의 수직선이 이 선분과 교차하기 위해서는 $x1 \le a \le x2$ 이여야 한다.

$y = b$ 꼴의 수평선이 이 선분과 교차하기 위해서는 $y1 \le b \le y2$ 이여야 한다.

이 관찰을 통해, 이 문제를 indexed tree로 $O(N \lg N)$ 만에 해결할 수 있다.

x좌표의 트리, y좌표의 트리 두 개를 만들어야 하는데, 두 과정이 똑같으므로 x좌표의 트리에 대해서만 설명하겠다.

우선 indexed tree의 각 노드를 stack으로 잡는다.

모든 선분에 대해, 선분이 차지하는 x범위에 해당하는 트리의 노드에 선분을 push한다.

$x = b$ 꼴의 수직선이 주어졌을 때, b를 범위로 갖는 모든 노드의 stack에 있는 선분들을 pop하고 그 중에 최대값을 답으로 출력한다.

pop되는 선분들 중 이미 이전에 제거된 선분이 있을 수 있으므로 크기 N의 visit 배열을 만들어서 visit 체크가 안된 것만 최대값으로 갱신해주면 된다.

이 알고리즘의 시간복잡도가 커 보일 수 있다. 하지만 시간 복잡도는 $O(N \lg N)$ 이다.

까닭은 한 선분이 push되는 노드의 수는 최대 $2 \lg N$ 이다. 마찬가지로 한 선분이 pop최는 회수 또한 최대 $2 \lg N$ 이다.

push와 pop은 $O(1)$(constant time complexity) 이므로 전체 $O(N \lg N)$의 시간복잡도를 갖는다.

후문: 대회 당시에는 정신없고 빨리 풀어야된다는 조급함에 list로 push, pop을 안하고 불필요하게 Priority Queue를 사용해서 $O(N \lg^2 N)$에 해결했다..

A.cpp