Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——rmq与更多的思考

Posted by fanhqme at 2009-07-14 23:10:11 on Problem 3728
这题我的算法是这样的:
维护每个节点到它的第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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator