比如:
2 9
2 9
3 8
1 10
排序后:
1 10
2 9
2 9
3 8
过程如下:
1 10
Query(1)   0//查询大于1 的点的数目
Insert(10)
2 9
Query(2)   1
Insert(9)
2 9
Query(2)   2
Insert(9)
3 8
Query(3)   3
Insert(8)
result     6
线段树就非得插入线段么?

• 线段树就非得插入线段么? ==〉 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