segment-tree - 如何使用线段树和扫描线

Question

给定 300000 个段。考虑任何一对段：a = [l1,r1]和b = [l2,r2]。如果l2 >= l1和r2 <= r1，它是“好”对。如果a == b，则为“坏”对。过分来说，这是“坏”的一对。

如何使用段树和扫描线查找给定段中所有“好”对的数量？

Answer 1

以相对于其 l 值的升序对段进行排序，对于具有相同 l 值的对，以相对于其 r 值的降序对它们进行排序。

假设对于一个特定的 ，您想计算好对 (ai,aj) 的数量，使得 j < i。设 ai=[l1,r1] 和 aj = [l2,r2]。然后我们有 l2 <= l1。现在我们需要计算 j 的所有可能值，使得 r2 <= r1。这可以通过为所有 j 的 r 值维护一个段树来完成，使得 0 < j < i。查询第 i 个对后，用第 i 个段的 r 值更新段树。

来到分段树部分，在 r 的值上构建一个分段树。在更新段树中的 r 值时，将 1 加到段树中的 r 值上，并且要查询 r 的特定值，请查询 [0,r-1] 范围内的总和。这将给出适合给定细分的细分总数。

如果 r 的值很大，不适合线段树，则首先对值应用坐标压缩，然后将线段树用于压缩值。