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 00448242 at 2005-07-18 00:23:39 on Problem 2489
In Reply To:这题咋做呢？ Posted by:patina at 2005-07-18 00:19:39

Followed by:

可以说得详细点吗 (0) patina 2005-07-18 00:26:55
- Re:可以说得详细点吗 (76) 00448242 2005-07-18 00:30:08
  - 3x!可是他是说覆盖还是又重叠部分？ (82) patina 2005-07-18 16:40:59
    - 就是看不明白样例，为什么不是5呢 (0) patina 2005-07-18 18:04:51
      - 仔细看题 (0) frkstyc 2005-07-18 18:06:05
        =_= (0) patina 2005-07-18 18:12:37
        Two line segments are said to be overlapping if they intersect in an infinite number of points. (0) patina 2005-07-18 18:16:11
        不是5对吗？内详 (131) patina 2005-07-18 18:18:52
        sigh~~~~~~~~~ (10) frkstyc 2005-07-18 18:21:00
        18:21:00.0 (12) frkstyc 2005-07-18 18:21:14
        =_+ 我以为是(1 1 3 3) (12) patina 2005-07-18 18:25:08
        这也能看错... (0) c0500448242 2005-07-18 18:26:16
        也是有难度的 (0) frkstyc 2005-07-18 18:28:01
可是用线段树又怎么判重呢 (0) patina 2005-07-18 19:08:55
- 不用判重 (0) c0500448242 2005-07-18 19:11:17
  - 是不是遇到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