PS 이야기

입력으로 주어지는 두 점 $(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으로 잡는다.모든 선분에 대해, 선분이 차지하..