2019 SCPC Round 2 5번 풀이
문제 요약 $M \times M$ 격자판에 $N$ 개의 점이 찍혀 있다. 각 점에 대해서, 그 점은 왼쪽 아래로 하는 가장 큰 정사각형을 그리려 한다. 단, 정사각형은 $N$ 개의 점중 어떤 점이라도 내부에 포함시키면 안된다. 모든 점에 대해서 정사각형을 그릴 때, 모든 정사각형 변의 합을 구하시오. $2 \le M \le 10^9$, $1 \le N \le 500000$ 풀이 1. 먼저 2D Range Tree 를 써서 특정 직사각형 구간에 점의 개수를 $O(\log^2 N)$ 시간에 알 수 있다. 여기에...