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

是不是遇到count > 0那么就一定overlap了，于是重叠数 += count，但是可能在多个insert的过程中加，那岂不是多算了

Posted by patina at 2005-07-18 19:16:51 on Problem 2489
In Reply To:不用判重 Posted by:c0500448242 at 2005-07-18 19:11:17

Followed by:

没明白你的意思 (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