题解

• 模型：将区间按左端点排序，设公共长度为 $L$，左端点为升序数组 $a_1,\dots,a_n$。

• 相交判定：两个区间相交当且仅当左端点差小于 $L$。

• 预处理：

  • $next[i]$ = $min(j>i \mid a_j \ge a_i + L)$（选择第 $i$ 个后，下一次能选的最左位置）。
  • $R[i] = next[i]-1$（第 $i$ 个被选区间向右能覆盖到的最远下标）。

• DP 定义：$f[i]$ 表示从第 $i$ 个“尚未被覆盖”的区间开始，选出一组满足条件的方案数。

• 关键转移：第 $i$ 个必须被某个 $j\in[i, R[i]]$ 覆盖，于是

题目内容

对于给定的$n$个长度相同的区间，第$i$个区间的左端点为$l_i$，

右端点为$r_i$，且全部区间的长度$r_i-l_i+1$固定。

你需要从中任选若干个不同的区间，使得:

• 选定的区间两两不存在交集;
• 其余区间均至少与一个选定的区间存在交集。