算法合集之一類算法復(fù)合的方法(留存版)
【正文】 X+1 … t1 t a q(a) t t t t t t t t t X X X X X ?只有插入操作，所以一直在拆分區(qū)間，而不合并區(qū)間 ?讓時(shí)間倒流，把所有操作按照從后往前的順序處理，那么區(qū)間就一直都在被合并了 ?并查集 ?把這里每個(gè)區(qū)間看作是一個(gè)集合，并維護(hù)它們對(duì)應(yīng)的 q ?每次操作近似地認(rèn)為是均攤 O(1) 算法 2 ?對(duì)一個(gè)詢問 “A Y”，需要詢問 O(R/Y)個(gè)區(qū)間，最多 O(R)個(gè)區(qū)間 ?一次詢問的時(shí)間復(fù)雜度高達(dá) O(R) ?總時(shí)間復(fù)雜度 O(NR)，也不能解決問題 嘗試著優(yōu)化 ?算法 2的瓶頸在于一次詢問需要處理的區(qū)間可能非常多，但只會(huì)發(fā)生在很少當(dāng) Y非常小的時(shí)候 ?一個(gè)例子：當(dāng) Y，算法 2已經(jīng)可以接受了 ?我們可以對(duì)這部分很少
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1