boj 20193: 화려한 정사각형

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

20193번: 화려한 정사각형

2 <= K <= N <= 100, 000 인 N개인 점들 중, K개의 색깔을 모두 포함하는 가장 작은 정사각형을 찾는 문제이다.K개의 색깔을 모두 포함하는 가장 작은 정사각형의 한변의 길이를 출력해주면 된다.

---

Parametric Search

한 변의 길이가 R인 정사각형으로 K개의 색깔을 모두 포함할 수 있는가? 라는 결정문제로 바꾸어, K개의 색깔을 모두 포함하는 R의 최소값을 찾는다.

sweeping

예시 : R = 3, 빨강(2,2), 파랑(5,5)

각 점의 x좌표마다 [y, y+R] 구간에 +1을 업데이트하고, 각 점의 'x좌표 + R + 1'마다 [y, y+R]구간에 -1을 업데이트하면, 임의의 어떤 지점을 보았을 때, 그 값이 K라면 길이가 R인 정사각형 안에 K개의 점이 포함된다고 판단할 수 있다.

- x축 정렬
- 각 점의 x축 좌표마다 Segment Tree + Lazy Propagation을 이용하여 [y, y+R] 구간에 +1을 업데이트 한다.
- 각 점의 x + R + 1좌표마다 [y, y+R] 구간에 -1을 업데이트 한다.
- 정렬된 x축 좌표 순서대로 +1, -1을 업데이트해가며, 업데이트된 segment tree에서 max값을 구한다.
- max값이 K(색깔의 개수)와 같으면 K개의 색깔이 한 변의 길이가 R인 정사각형안에 모두 포함된다고 판단할 수 있다.

[예시]
- [2,5] 구간에 +1 update, max값은 1.
- [5,8] 구간에 +1 update max값은 y가 5일 때 2.
- [2,5] 구간에 -1 update
- [5,8] 구간에 -1 update


중복 확인

예시 : R = 3, 빨강(2,2), 빨강(5,5)

sweeping을 하면서 구간 업데이트를 해준 후, max값을 구하는 segment tree query를 통해 max값이 K이면 한 변의 길이가 R인 정사각형안에 K개의 색깔이 모두 포함된다고 판단할 수 있다.
그런데, 위의 그림과 같이 [2,5]구간에 +1을 update, [5,8]구간에 +1을 업데이트를 해준다면, [5]지점은 동일한 색깔로 중복 업데이트되어 value 2를 가지게 되어 문제가 된다. 동일한 색깔이 중첩되는 구간의 경우, value 1만 가지게 하고 싶다.
이전에 +1을 update한 이력을 찾은 후, 중복되는 구간은 제외한 후 [6,8]에만 업데이트해주어야 한다.

- K개의 multiset을 이용.
- +1 update할 때 해당 색깔의 multiset에 y값을 insert.
- 차후, +1을 구간 update할 때, multiset을 이용하여 중복된 구간을 제외한 구간만 +1을 업데이트 해준다.
- -1을 구간 update할 경우도 마찬가지로 중복된 구간을 제외한 구간만 -1을 업데이트 해준다.

[예시]
- [2,5] 구간을 +1 update 할 때, multiset에 2를 insert.
- [5,8] 구간을 + 1update할 때, multiset에 5보다 작은 최대값을 찾음 (2)
- [2, 2 + R(3)] 구간은 +1 update시 제외되어야 하는 구간이므로, [6,8] 구간만 +1 update.
- [2,5] 구간을 -1 update할 때, multiset에 2보다 큰 최대값을 찾음 (5)
- [5, 5 + R(3)] 구간은 -1 update시 제외되어야 하는 구간이므로, [2,4] 구간만 -1 update.

---

- Parametric Search에 O( log(max좌표값) ), sweeping에 O(NlogN) 시간복잡도가 소요되어, 전체 시간복잡도는 O(N*logN*log(max좌표값) ).

참고 : https://justicehui.github.io/koi/2021/03/07/BOJ20193/