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

有没线性算法呢?

Posted by ArXoR at 2005-06-26 19:02:59 on Problem 2452
In Reply To:难得我写了个线段树呢 Posted by:uni at 2005-06-26 18:12:27

Followed by:

用RMQ+D&C就应该是O(n)的吧 (0) frkstyc 2005-06-26 19:03:43
- 呃...好像对哦,汗...我没分治,迭代了一下 (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
Re:有没线性算法呢? (15) Lucifer 2005-09-05 16:05: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