Detail of message

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

预处理是O(n)，每条查询是O(1)，对于最坏的情况，几乎每两个点都要算一次RMQ

Posted by xiaomi at 2004-12-17 21:13:15 on Problem 1741
In Reply To:我觉得因为±RMQ算法整个是N杂度,所以不会到N^2啊 Posted by:LIANGLIANG at 2004-12-17 20:54:45

Followed by:

了解了,其实我觉得可以借鉴2114的标程的方法,nlogn的复杂度 (0) LIANGLIANG 2004-12-17 21:21:10
有一种类似归并排序的方法，一会儿试试 (0) xiaomi 2004-12-17 21:28:32
- 是用来解决类似2104的中的查询那种方法吗? (0) LIANGLIANG 2004-12-17 21:37:00
  - 不是，是树形dp+归并排序，我明天再写吧，刚才作sgu被卡了 (0) xiaomi 2004-12-17 22:55:43
    - Re:不是，是树形dp+归并排序，我明天再写吧，刚才作sgu被卡了 (49) wisdom 2005-01-19 15:43:55
Re:预处理是O(n)，每条查询是O(1)，对于最坏的情况，几乎每两个点都要算一次RMQ (16) cykt165883399 2007-07-09 16:19:11

Post your reply here:

Home Page Go Back To top

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