BOJ 23299 - 화질 - 자동 (480p)

image.png

Offline Dynamic Connectivity를 Disjoint Set이 아닌 Knapsack과 함께 쓰는 문제이다.

결국 ODC에서 분할정복이라는 것은 [s,e][s,e] 인 구간에 대해 log⁡(e−s)\log (e-s) 개의 서로 다른 구간에서 검사를 해준다는 것이 된다.

따라서 O(Nlog⁡N)O(N \log N) 번 Knapsack의 결과를 push했다 pop 했다 하면 되므로 O(NWlog⁡N)O(NW \log N) 만큼의 시간으로 풀 수 있다.

Tags:

Categories:

Updated:

Comments

You may also enjoy