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 c0500448242 at 2005-07-18 19:11:17 on Problem 2489
In Reply To:可是用线段树又怎么判重呢 Posted by:patina at 2005-07-18 19:08:55

Followed by:

是不是遇到count > 0那么就一定overlap了，于是重叠数 += count，但是可能在多个insert的过程中加，那岂不是多算了 (0) patina 2005-07-18 19:16:51
- 没明白你的意思 (0) xfxyjwf 2005-07-18 19:19:35
  - 就是比如在x轴上，已经在线段树上插入了(1, 10), 再插入(2, 9)，那么怎么实现计算重叠?我想的方法会有重复的 (0) patina 2005-07-18 19:33:30
    - 按左端点排序, 插入右端点 (221) c0500448242 2005-07-18 19:42:29
      - 线段树就非得插入线段么? ==〉 Good!真好人。=_+ (273) patina 2005-07-18 19:46:20
        感觉这样的更像是static bst而不像是segment tree了 (0) frkstyc 2005-07-18 19:51:12
        你怎么做的? (0) c0500448242 2005-07-18 19:52:37
        你猜…… (0) frkstyc 2005-07-18 19:53:25
        我猜啊...汇编 (0) c0500448242 2005-07-18 19:55:35
        呵呵，你要把整个题重新想一遍了 (0) frkstyc 2005-07-18 19:56:12
        这人写程序怎么那么快？？？？？ (0) frkstyc 2005-07-18 19:55:19
        嗯, 而且一次就AC (0) c0500448242 2005-07-18 19:56:29
        调过了样例就交了，看来算法对很重要，不过，我的巨慢无比 (0) patina 2005-07-18 20:22:55
        能在时限内出来就可以了，TUD比赛的时候这个题限90秒 (0) frkstyc 2005-07-18 20:25:47
        但是我很想知道别人怎么<1000ms的，:) (0) patina 2005-07-18 20:27:16
        我也想知道 (0) c0500448242 2005-07-18 20:33:55
        呵呵，好好想想吧，想办法把O(nlogn)-O(nlogn)搞成O(nlogn)-O(n)就行了 (0) frkstyc 2005-07-18 20:42:41
        斜率相同的那些线段覆盖大概也许似乎的确可以做到O(n)??那就不能排序了....怎么搞呢？ (0) palmtenor 2005-07-18 20:47:05
        我说的同组统计的时间，分组还是要O(nlogn)的 (0) frkstyc 2005-07-18 20:48:11

Post your reply here:

Home Page Go Back To top