백준 17671 두 안테나 (JOISC 2018/2019 Day 2 1번) [D1]

백준 17671 두 안테나 (JOISC 2018/2019 Day 2 1번) [D1]

728x90

문제 설명(링크)

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

문제 요약

안테나가 일렬로 $N$개 있다. 각 안테나는 높이가 있다. 이때 두 안테나 i와 j가 있어서 i가 j에게 메세지를 보낼 수 있을 조건은 i와 j의 거리가 $[A_i, B_i]$사이에 포함되는 것이다. $Q$개의 쿼리가 주어지는데, $[l,r]$사이 안테나 중 서로 통신할 수 있는 두 안테나 중 안테나의 높이 차이가 최대가 되는 쌍의 높이 차이를 구하는 쿼리이다.

풀이

서브테스크를 풀고, 짧게는 몇시간쯤, 길게는 1일 정도 삽질하다 보면 그럴듯한 풀이가 나오고, 실제로 된다.

두 안테나가 통신할 수 있는 조건이 특이하다. 한 안테나를 보면 그 안테나가 메세지를 보낼 수 있는 안테나의 범위가 특이한데,

______ (안테나) ______

대충 이렇게 생겼다.

뭔가 이 그대로 처리하기는 어려워 보이니, 다음과 같은 아이디어를 사용한다.

이차원 배열 ${arr_{k,i}}$를 만들어서 $arr_{k,i}$에는 i번 안테나와 통신 가능한 안테나 중 $[i, k]$ 범위에 있는 안테나만 고려해 i번 안테나와의 높이차의 최대를 저장한다. 즉, 오른쪽 범위를 저장하는 것이다. 이렇게 한다면 쿼리 $[l,r]$을 $arr_{r, l}, ..., arr_{r, r}$사이 최댓값을 구하는 방식으로 풀 수 있다. 그러면, 처음에 배열 ${arr_1}$을 만들고 이를 업데이트해서 ${arr_2}, ..., {arr_{N-1}}$순으로 차례로 구하는 방식으로 쿼리를 전부 처리하는 방식을 생각할 수 있다.

우선, 배열을 업데이트하는 방법부터 알아보자. ${arr_{k-1}}$을 ${arr_k}$로 업데이트할 때, $[k-B_k, k-A_k]$사이 범위에 있는 안테나 중 $k$번 안테나에 메세지를 보낼 수 있는 안테나의 인덱스의 값만 갱신된다. 그러면 여기서 다음과 같은 항목을 포함하는 세그먼트 트리를 생각할 수 있다.

1. 노드에 해당하는 구간의 arr값의 최댓값인 $maxvalue$

2. 노드에 해당하는 구간에 있는 안테나 중 $k$번(수시로 바뀜) 안테나와 통신할 수 있는 안테나 중 높이가 최대인 것과 최소인 것의 높이

3. 레이지(아래에서 설명할것임)

일단, 배열 업데이트는 이런 식으로 이루어진다.

"[a, b] 범위 사이에 k번 안테나와 통신할 수 있는 모든 안테나는 arr값을 갱신하라"

레이지에서는 한 노드에 요청된 업데이트 쿼리 중 k값의 가장 작은 것과 큰 것을 저장한다.

만약 한 노드에 저 명령이 전달되면, 그 노드는 자신의 $maxvalue$를 2번 항목(바로 위의)의 $k$번 안테나와 통신 가능한 최대 높이와 최소 높이를 고려하여 갱신한다. 또한 그 후에 lazy 연산을 자식 노드에 전파시킨다.(레이지니, 당연시 자식노드에서 바로 실행되지는 않는다.) 그러면 $k+1$번 안테나에 대한 업데이트 연산은 어떻게 할까? 이는 2번 항목인 $k$번 안테나와 ...높이 항목이 변한다. 이는 초기에 각 안테나가 통신할 수 있는 범위를 구해놓고, $k$번 안테나에서 $k+1$번 안테나로 오면서 추가로 통신 가능해지게 되는 안테나와, 그 반대로 통신이 불가능해지게 되는 안테나를 구해 놓고, 탑다운으로 레이지를 잘 전파해 나가면서 2번 항목을 갱신하면 된다.

쿼리는 평범한 RMQ와 비슷하게, 탑다운 방식으로 노드에 도착하면 연산을 자식노드에 전파해 가면서 하면 된다.

소스코드

나중에 추가 예정. oj.uz에 잘 뒤져보면 있음

총평

재밌는 문제다. 기숙사에서 누워있다가 생각났다. 처음에는 Splay Tree를 생각했으나(사실 그러면 풀이가 더 직관적이고 깔끔하게 보인다) 스플레이를 구현하는 것 외에도 좋은 풀이가 있을 것이라 생각하여 이 풀이를 생각했다.

시험이 얼마 안 남아서, 곧 PS일지가 올라갈 예정이다.

728x90

from http://flappybird.tistory.com/51 by ccl(A) rewrite - 2021-10-06 01:01:02