如何使用线段树和扫描线

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

进入分段树部分，根据r的值构建分段树。在更新分段树中的r值时，将分段树中的r的值加1，并查询r的特定值，查询范围为0，r-1的sum。这将给出适合给定分段的分段总数。

如果r的值太大，无法放入段树中，则首先对值应用坐标压缩，然后使用段树作为压缩值。