#소개
2022/2023 JOISC 3-3 기출 문제로, 난이도는 solved.ac 기준 Diamond II입니다.
제 풀이가 정해와 달라 풀이를 작성해보려고 합니다.
#문제 요약
- $N$개의 정점을 가진 트리 형태의 섬들과, $M$개의 관광 명소가 각각 섬 $C_1, C_2, ... , C_M$에 위치해 있다. 다음과 같은 $Q$개의 쿼리를 처리해야 한다.
- $L\text{ }R$ : $C_L, C_{L+1}, ... , C_R$까지의 섬을 모두 방문하기 위해 지나야 하는 섬들의 최소 개수를 출력한다.
- $1 \le N, M, Q \le 100,000$
#사용한 알고리즘
- 세그먼트 트리
- 최소 공통 조상
- 오프라인 쿼리
- 오일러 경로 테크닉
- 희소 배열
#풀이
*다음과 같이 정의합니다.
$C_1, C_2, ... , C_k$의 경로 : $C_1, C_2, ... , C_k$의 섬을 모두 방문하기 위해 지나야 하는 섬들의 집합
먼저, $R=M$과 같이 고정되어 있다고 생각해봅시다.
$C_1, C_2, ... , C_M$ 각각에 대해, $($$C_{i+1}, C_{i+2}, ... , C_M$의 경로에 $C_i$를 추가할 때 집합에 새로 넣어야 하는 노드의 개수$)$를 구하면, 세그먼트 트리로 이들의 누적 합을 구해 쿼리의 답을 구할 수 있습니다. 이때 각 항을 $add[i]$라고 정의합시다.
각각의 값은 $C_{i+1}, C_{i+2}, ... , C_M$의 경로 중 $C_i$와 가장 가까운 점과 $C_i$ 사이 간선의 개수와 같습니다.
이때 어떤 노드가 경로에 포함되면, 그 노드의 부모도 경로에 포함되므로 $($$C_{i+1}, C_{i+2}, ... , C_M$ 모두의 LCA의 경우 그렇지 않지만, 고려하지 않아도 큰 문제가 없습니다.$)$ $C_i$의 조상 노드들 중 경로에 포함되는 가장 작은 노드를 구하면 됩니다.
오일러 경로 테크닉과 희소 배열을 이용한 이분 탐색으로 $add[i]$를 $O(log^2 N)$의 시간에 구할 수 있습니다.
하지만, 이 경우 $C_M$을 잘 처리하지 못하므로 $C_M$에 대해 예외 처리를 해 줘야 합니다.
- $i\ M$ 의 쿼리를 처리해야 할 경우, $C_{i+1}, C_{i+2}, \dots, C_M$ 모두의 LCA를 구하고, $C_M$과의 깊이 차이에 1을 더해 주면 $C_M$에 대해 고려해 주어야 하는 값을 구할 수 있습니다.
이는 LCA 세그먼트 트리를 만들면 역시 $O(\log^2 N)$의 시간에 구할 수 있습니다.
fig 2) 5와 가장 가까운 경로상의 점은 1이므로 5~1 사이 노드를 모두 집합에 추가해 줍니다.
fig 3) 4와 가장 가까운 경로상의 점은 2이므로 4~2 사이 노드를 모두 집합에 추가해 줍니다.
이제 위에서 찾은 성질과 오프라인 쿼리를 이용해 풀이를 찾아 봅시다!
$R$을 $1$부터 $m$까지 이동시키며 구간합 세그먼트 트리를 갱신해 줍시다.
오일러 경로 테크닉으로 만든 세그먼트 트리의 각 노드에는 "이 노드를 루트로 하는 서브트리의 점이 새로 경로에 추가될 때 갱신해야 하는 $add[i]$의 번호"가 담겨 있습니다. 갱신할 $add[i]$가 없다면 $0$이 있습니다. 이를 $up[i]$라고 합시다.
$($만약 갱신해야 하는 번호가 2개 이상이라면 그들의 LCA가 해당 노드보다 더 아래에 있으므로 해당 노드의 추가에 의해 갱신되지 않아 모순이 됩니다.$)$
sparse table 이분 탐색을 이용해 나의 조상 노드들 중 나와 $up[i]$ 값이 다르며 가장 가까이에 있는 점을 $O(log^2 n)$ 시간에 구할 수 있습니다. 더 이상 갱신할 점이 없을 때까지 갱신해주면 됩니다.
$($이때 총 갱신 횟수는 $O(M)$입니다. 증명은 AC로 대신합니다.$)$ 따라서 총합 $O(Mlog^2 n)$에 갱신이 가능합니다.
각각의 쿼리를 계산하는 시간이 $O(log^2 N)$, 세그먼트 트리 갱신에 필요한 시간이 총 $O(Mlog^2 N)$이므로, 결과적으로 $O\text{((}M+Q\text{)}log^2 N\text{)}$의 시간복잡도로 문제를 해결할 수 있습니다.