计算在给定范围内的间隔数

Question

假设您有一个间隔列表，例如[（0 4），（1 3），（2 5），（2 6）]。此列表未排序。然后给您一个范围，如[1 5]。您必须返回适合范围内的间隔数。在这个问题中，它将返回2。（（1 3）和（2 5））

间隔列表保持不变，但我们最多得到100000个查询，每个查询由一个范围组成。对于每个范围查询，我们必须返回适合其中的间隔数。

在研究之后，我读到了间隔树。但是，您只能查询与任何给定范围重叠的间隔，而我正在查找该范围内的间隔。这些查询需要对数时间。

是否有任何方法可以在类似的时间复杂度下解决此问题，可能是使用区间树的变化？我不是在寻找线性解决方案（因为暴力意味着扫描所有间隔）。

Answer 1

假设这些线段没有那么长，如果你要添加一个间隔，你可以在树的节点中记住id，你只需要记住穿过点a和b的线段，所以你只需要让线段树获得id穿过a和b的向量。从另一棵树，您将询问a-b段中的结尾数。之后，您只需删除发生过一次的id。它应该更快。