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