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(nlogn)都不能过的玩一玩

Posted by sunmoonstar_love at 2006-11-08 14:57:12 on Problem 3080
In Reply To:这个不就是去年成都那道题的简化版么…… Posted by:wywcgs at 2006-11-08 12:52:55

Followed by:

那O(n)也不见得能过吧，O(n)的系数…… (32) wywcgs 2006-11-08 14:58:40
- 这个没考虑到, O(n)的系数比 O(nlgn)的系数*lgn大多少 (36) sunmoonstar_love 2006-11-08 15:00:59
  - 没测试，我写的O(nlogn)巨慢无比 (61) wywcgs 2006-11-08 15:04:04
    - 明天玩一下 (65) sunmoonstar_love 2006-11-08 15:54:50
    - 似乎在规模不超过50万的时候O(n)的rmq pk O(nlogn)的rmq没有优势, 因为O(nlogn)rmq查询代价比O(n)rmq小得多 (65) sunmoonstar 2006-11-09 16:18:39
- 这题怎么转化成RMQ？？？ (36) waterine 2006-11-08 19:34:05
- 后缀数组+rmq (36) wywcgs 2006-11-08 19:34:49

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