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