BOJ 23299 - 화질 - 자동 (480p)
Offline Dynamic Connectivity를 Disjoint Set이 아닌 Knapsack과 함께 쓰는 문제이다.
결국 ODC에서 분할정복이라는 것은 $[s,e]$ 인 구간에 대해 $\log (e-s)$ 개의 서로 다른 구간에서 검사를 해준다는 것이 된다.
따라서 $O(N \log N)$ 번 Knapsack의 결과를 push했다 pop 했다 하면 되므로 $O(NW \log N)$ 만큼의 시간으로 풀 수 있다.
Comments