最近比较烦。
好多事情， 感觉最近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
豪 阅读(564)
评论(4) 编辑 收藏 引用 所属分类:
生活感想