最近比較煩。

好多事情， 感覺(jué)最近acm強(qiáng)度大了不少， 學(xué)了bst和interval Tree, 可就是知道它的模型， 不能夠?qū)嶋H應(yīng)用， 不過(guò)感覺(jué)interval tree用起來(lái)會(huì)比bst安全， 我怎么分析bst都會(huì)退化成o(n^2)的， 唉， 好像白學(xué)了， 不過(guò)聽(tīng)說(shuō)靜態(tài)bst不會(huì)退化， 看了lirui的論文， 好像它寫(xiě)的靜態(tài)bst的建樹(shù)是基于一組已排列好的數(shù)， 然后通過(guò)中序遍歷， 建立一個(gè)平衡的bst,? 所以不會(huì)退化， 但是如果每次都要去排序的話(huà)， 那不是浪費(fèi)了nlogn的時(shí)間了？疑惑啊!

而感覺(jué)用interval tree比較安全， 至少tle的情況比較小(我的動(dòng)態(tài)bst TLE了無(wú)數(shù)次)， 但是interval tree的模型分析難度比較大， 對(duì)于特定的問(wèn)題的cout[i]的分析， 還有特定問(wèn)題要加入的維護(hù)信息， 都是夠令人頭痛的， 唉， 現(xiàn)在想想， 當(dāng)初學(xué)并查集的時(shí)候多過(guò)癮， 學(xué)完了馬上就能應(yīng)用了， 現(xiàn)在可痛苦了。。。

樹(shù)的應(yīng)用， 模型的建立， 信息的維護(hù)方法， 我已經(jīng)兩晚睡不著了， 開(kāi)始懷疑， 搞acm， 會(huì)不會(huì)短幾年命？-_-