ODC

뭔가 PBS같은 느낌을 받았다. 둘다 분할정복 기반의 알고리즘이라서 그런가? PBS는 쿼리들에 대해 이분탐색 구간에 대한 분할정복이고 ODC는 쿼리들의 Life구간에 대한 분할정복을 한다.

다른점은 PBS에서는 쿼리분할하기 위해 특정자료구조의 ~이하(이상)인것 들이 저장되어있으면 되는데, ODC는 ~이하(이상)가 아니라 현재시간구간을 완전히 포함하는 Edge들이 저장되어있어야 하기 때문에 PBS와는 다르게 Undo가 효율적으로 가능해야 한다.(PBS는 각 level별로 자료구조 하나씩 할당해두고 dfs순서로 처리해주면 됨)

쿼리를 나눌때 m기준 왼쪽과 오른쪽에 둘다 걸치는 쿼리의 경우 두개로 복제되는데, 시간복잡도가 어떻게 보장되는건지 좀 더 이해할 필요가 있을듯. [내용추가]:중복없이 그냥 나눠지면 분할정복 각각 O(N)이라 NlogN인데 중복이 있어서 log^2이 되는듯. 겹치는부분은 분할정복하기 때문에 한 구간에 대해 최대 logN번 생겨서 amortized하게 log가 더 붙어 총 log^2이 되는거같다.그러면 unionfind복잡도는 곱하기 적용되는게 아닌건가? 모르겠다 그냥 복잡도분석이 어려움.

세그트리 쓰는사람도 있던데 분할정복을 세그로 하는게 아니면 어디에 세그가 필요한건지 잘 모르겠다

https://codeforces.com/blog/entry/15296 이거보면 구간을 미리 세그에 할당하면 NlogN개가 되고, 각 분할마다 유파로그 붙이면 KlogK가 걸려서 뭐 마스터정리 해보면 로그제곱되는거같다?