段组合中的连接组件

Question

我在一维数字线上有N个分段（1≤N≤10 ^ 5）。每个线段都包含所有实数x，使得起点≤x≤终点。

我们可以说，一组片段的“联合”是至少一个片段中包含的所有x的集合。一组线段的“复杂性”是以其并集表示的连接区域的数量。

在段的所有2 ^ n个子集中，我们要计算复杂度之和。

示例：

您有三个段，[1，6]，[2，3]，[4，5]，其中[a，b]中a =起点，b =终点。

解决方案为8。这是每个子集的复杂性：[1,6]⟹1，[2,3]⟹1，[4,5]⟹1

{[1,6]，[2,3]}⟹1，{[1,6]，[4,5]}⟹1，{[2,3]，[4,5]}⟹2] >

{[1,6]，[2,3]，[4,5]}⟹1

答案是1 + 1 + 1 + 1 + 1 + 2 + 1 = 8。

显然，我们不能遍历所有子集（2 ^ N个子集！）有人可以给我提示或向正确的方向推我吗？

我在一维数字线上有N个分段（1≤N≤10 ^ 5）。每个段包含所有实数x，以使起点≤x≤终点。我们可以说一组段的“联合”是所有...的集合...

Answer 1

按终点对线段进行排序。由于空的点子集的“复杂度”为零，因此对于每个段S足以计算最右边的段为S的每个子集的复杂度之和。用Sum（S）表示该数量。令Count（S）为最右边间隔为S的子集数。

Sum(S) = sum_{segments T left of S where T doesn't overlap S} (Sum(T) + Count(T)) +
         sum_{segments T left of S where T does overlap S} Sum(T)
Count(S) = 2^{number of intervals to the left of S},