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

用RMQ+D&C就应该是O(n)的吧

Posted by frkstyc at 2005-06-26 19:03:43 on Problem 2452
In Reply To:有没线性算法呢? Posted by:ArXoR at 2005-06-26 19:02:59

Followed by:

呃...好像对哦,汗...我没分治,迭代了一下 (0) ArXoR 2005-06-26 19:07:05
光RMQ就有nlogn了，怎么可能到O(n)呢？看来我的RMQ+D&C7xxms的成绩已经没有优化余地了~~~~~ (0) palmtenor 2005-07-29 22:03:30
- re (0) palmtenor 2005-07-29 22:20:07
  - b4 (0) frkstyc 2005-07-29 22:29:46
    - 遭bs的不是你么...... (0) palmtenor 2005-07-29 22:30:56
      - 显然是palmtenor，利用LCA搞就可以做到O(n)，你还是去多吃点饭吧 (0) frkstyc 2005-07-29 22:34:42
        我知道可以用RMQ做到o(n)的LCA....能反过来么？ (0) palmtenor 2005-07-29 22:42:40
        所以说你要吃饭 (0) frkstyc 2005-07-29 22:43:54
        您告诉我吧.....拜.....我只知道+-1的RMQ能做到O(n).... (0) palmtenor 2005-07-29 22:51:35
        bg我和TN吧 (0) frkstyc 2005-07-29 22:51:52
        西门鸡翅...... (0) palmtenor 2005-07-29 22:58:49
        也成 (0) frkstyc 2005-07-29 23:00:04
        greedy````` (0) palmtenor 2005-07-29 23:00:55
        一般RMQ问题可以用迪卡尔树转化为+-1RMQ问题 (0) Spacesheep 2005-08-24 13:05:11
        那天赫然发现srbga上就有讲....会了````` (0) palmtenor 2005-08-24 13:48:57

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