最近比較煩。
好多事情， 感覺最近acm強度大了不少， 學了bst和interval Tree, 可就是知道它的模型， 不能夠實際應用， 不過感覺interval tree用起來會比bst安全， 我怎么分析bst都會退化成o(n^2)的， 唉， 好像白學了， 不過聽說靜態bst不會退化， 看了lirui的論文， 好像它寫的靜態bst的建樹是基于一組已排列好的數， 然后通過中序遍歷， 建立一個平衡的bst,? 所以不會退化， 但是如果每次都要去排序的話， 那不是浪費了nlogn的時間了？疑惑啊!
而感覺用interval tree比較安全， 至少tle的情況比較小(我的動態bst TLE了無數次)， 但是interval tree的模型分析難度比較大， 對于特定的問題的cout[i]的分析， 還有特定問題要加入的維護信息， 都是夠令人頭痛的， 唉， 現在想想， 當初學并查集的時候多過癮， 學完了馬上就能應用了， 現在可痛苦了。。。
樹的應用， 模型的建立， 信息的維護方法， 我已經兩晚睡不著了， 開始懷疑， 搞acm， 會不會短幾年命？-_-
posted on 2006-09-06 02:32
豪 閱讀(600)
評論(4) 編輯 收藏 引用 所屬分類:
生活感想