Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
雁过留声——rmq与更多的思考这题我的算法是这样的: 维护每个节点到它的第2的i次方个祖先中这些值: 第1<<i辈祖先的指针 最小价格 最大价格 最大收益(从自己走到祖先) 最大收益(从祖先走到自己) rmq(nlogn的那个)的精髓就是记录自己以及以后的1<<i个值中的最值,照搬到图上,就成了这个算法。有一点dp的味道,也有一点SegmentTree的味道。 对于每个查询,求一次LCA(用dfs+RMQ实现),然后“区间分解”,再合并。 一下几个网址对这题有帮助: LCA: http://hi.baidu.com/tangchenxing/blog/item/5861438f46dcdaff513d92fe.html RMQ: http://baike.baidu.com/view/1536346.htm Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator