백준 온라인 저지 - 16336. Points and Rectangles

https://www.acmicpc.net/problem/16336

16336번: Points and Rectangles

SEERC 2018년 K번 문제이다.

 

2차원 정수 좌표계에서 쿼리가 $Q$개 들어온다.($Q \leq 10^5$) 초기에 점들의 집합 $P_0$와 직사각형들의 집합 $R_0$는 공집합이다. $i$번째 쿼리가 주어짐에 따라 두 집합 중 하나에 원소가 추가된다.

($i$번째) 쿼리는 아래 둘 중 하나이다.

• 1 x y : 점 $(x, y)$를 입력 받아 $P_i = P_{i-1} \cup \{(x, y)\}$ 로 원소를 추가한다.
• 2 x1 y1 x2 y2 : 직사각형 $(x_1, y_1, x_2, y_2)$를 입력 받아 $R_i = R_{i-1} \cup \{(x_1, y_1, x_2, y_2)\}$ 로 원소를 추가한다. 이는 $(x_1, y_1)$을 좌하단, $(x_2, y_2)$를 우상단 꼭짓점으로하는 각 변이 $x$, $y$축과 평행한 직사각형이다.

($i$번째) 쿼리가 주어진 직후 아래 집합의 크기를 출력한다.

$$\{ (p, r) : p \in P_i,\: r \in R_i,\: \text{$p$는 $r$ 안에 위치함} \}$$

단, 점이 직사각형 안에 위치할 조건은, 그 점이 직사각형의 내부 혹은 둘레에 위치해야한다는 것이다.

 

 

 

CDQ 알고리즘을 적용하여 2차원 오프라인 쿼리로 분할 정복할 수 있는 문제이다.

이 개념이 생소하다면 아래 포스팅을 꼭 읽도록 하자.

 

https://lego0901.tistory.com/19?category=757498

CDQ 알고리즘 (분할 정복을 이용한 오프라인 쿼리 최적화)

 

 

당연히 좌표 압축을 통하여 다루는 모든 좌표값이 양의 정수이자 1부터 시작하는 연속적인 값을 가진다고 가정하자.

 

만약 $i$번째 쿼리가 점으로 들어온다면 직전의 출력값에서 $| \{r : r \in R_{i-1},\: \text{$p_i$는 $r$ 안에 위치함} \} |$ 을 추가해주면 된다. 점이 아니라 직사각형이라도 비슷하게 더해주면 된다.

즉, $i-1$번째 쿼리에 대한 출력값에서 얼마만큼 더 출력값이 증가했는지 합하는 방향으로 문제를 풀어보자.

 

직사각형에 대한 부분을 다루는 부분이 까다롭다.

2차원 부분합을 다루듯 4개의 영역으로 쪼개고 각 영역에 가중치를 부여하자.

• $(0, 0, x_1 - 1, y_1 - 1)$ 직사각형 영역에 가중치 1
• $(0, 0, x_1 - 1, y_2)$ 직사각형 영역에 가중치 -1
• $(0, 0, x_2, y_1 - 1)$ 직사각형 영역에 가중치 -1
• $(0, 0, x_2, y_2)$ 직사각형 영역에 가중치 1

모든 직사각형을 원점을 한 꼭짓점으로 가지도록 만들었다. 그러므로 직사각형 또한 원점의 맞은편에 위치한 꼭짓점 좌표로써 2차원 좌표형식 $(x, y)$로 표현할 수 있다. (앞으로 직사각형을 이렇게 표현하겠다.)

 

가중치에 대한 얘기를 하면 쿼리를 처리하는 방향도 더 명확해진다.

• 만약 $i$번째 쿼리로 점이 들어온다면, 그 점을 포함하는 이전에 추가된 모든 직사각형 영역들의 가중치 합으로 $i$번째 답의 증가량을 계산한다.
• 만약 $i$번째 쿼리로 직사각형이 들어온다면, 그 영역에 포함되는 이전에 추가된 모든 점들의 개수에 가중치를 곱하여 $i$번째 답의 증가량에 합한다.

 

 

점 $(x, y)$가 직사각형 $(a, b)$ 안에 위치할 필요충분조건은 $x \leq a \wedge y \leq b$ 이다.

 

모든 쿼리를 $(i, x, y, w)$ 형태로 모으자. $i$는 쿼리의 순서를 의미하고, $w$는 가중치를 의미한다. 만약 $i$번째 쿼리가 점이라면 $w$는 편의상 0으로 둔다.

 

$i$번째 쿼리를 수행한 직후 출력값의 증가량은 $i' \leq i \wedge x' \leq x \wedge y' \leq y$를 만족하는 무언가의 개수나 가중치의 합을 구하는 것과 같다.

 

CDQ 알고리즘의 원형에 가까워졌다.

 

 

단, 분할 정복을 두 번 사용해야 한다. 한 번은 점을 추가하는 쿼리를 처리할 때 사용하고, 나머지는 직사각형을 추가하는 쿼리에 사용한다.

 

 

 

(소스코드 삭제)