> 例如这组数据
> 3
> 1 10
> 1 3
> 6 10
> 显然有三个poster可见，1-3，4-5，6-10
> 但排序离散化之后：
> 排序后：1 1 3 6 10
> 离散化后：1对应1，3对应2，6对应3，10对应4
> 原始数据的三个区间就变为：
> 1 4
> 1 2
> 3 4
> 结果可见的poster就只有两个，1-2，3-4。。。。。


这个是没问题的，我们可以在存入时作如下处理
将起始点值不变，而将结束点的值加1
这样就将原题中的点树（即每个叶节点中储存的值是1-1，2-2……这样的树）转化为线段树（即每个叶节点中存的是1-2，2-3……这样的树）
这样的话
上述数据在离散化后仍会变为
1 4
1 2
3 4
但在检索时2-3这个区间就会被检索到。
这样做对
3
1 10
1 5
6 10
这样的数据也不会有影响

• Re:我觉得离散化会有问题 (317) heimengnan 2009-11-23 10:03:30
  • 这样离散不会有问题 (397) haiwei624 2010-01-16 17:49:56
    • Re:这样离散不会有问题 (48) heimengnan 2010-03-22 12:51:40
    • Re:这样离散不会有问题 (377) Mghost 2010-09-07 17:03:58