Solution - P6146 [USACO20FEB]Help Yourself G

P6146 [USACO20FEB]Help Yourself G

idea：

熟悉使用计数类问题的常用方法：设函数并通过分类讨论找到递推式，不需要多余的计算。

解决方案：

我们先按左端点给所有序号排序。

设 $f_i$ 表示前 $i$ 条线段的 $2^i$ 种方案的复杂度总和。

现在考虑递推计算 $f_i$ 。

假设现在加入第 $i$ 条线段。有以下两种情形：

1. 不选第 $i$ 条线段。

答案是显然的： $f_{i-1}$ 。

2. 选择第 $i$ 条线段。

设第 $i$ 条线段和之前的 $k$ 条线段相交。当这 $k$ 条线段被选择时，第 $i$ 条线段不能产生贡献，其他情形贡献均为 $1$ 。

故答案为： $f_{i-1} + 2^{i-1-k}$ 。

$k$ 是可以均摊 $O(n)$ 求得的。

故我们得到了递推式：

$$f_i = 2\cdot f_{i-1} + 2^{i-1-k}$$

总时间复杂度 $O(n\log n)$ 。用桶排加预处理 $2^{0...n}$ 应该可以做到 $O(n)$ 。