题解：P17140 [NOI 2026] 线段（暂无数据）

· · 题解

简单题吧，与 BIM_XY 讨论了一会就会了。

最终树的形态绝对的是一条链上挂了一堆长度为 1 的链。

考虑对区间左端点排序后直接 DP。

设 dp_{i,r,R,t} 为考虑前 i 条线段，选择的线段次大的右端点为 r，最大的为 R，选了 t 条线段。

设第 i 条线段为 [l_i,r_i]。

第一个转移式子，左端点在 (r,R] 内，右端点 \le R，此时只会改变 r，所以可以枚举每个 R，进行更新，dp_{i,r_i,R,t+1}=\sum_{r<l_i}dp_{i-1,r,R,t}。

第二个转移式子，左端点在 (r,R] 内，右端点 > R，此时只会改变 R，所以可以枚举每个 r，进行更新，dp_{i,r,r_i,t+1}=\sum_{R<r_i}dp_{i-1,r,R,t}。

第一维先给滚动数组滚掉，但是这还是不够。

发现因为随着 i 的增加，因为 l_i>r，所以随着 r 的转移，线段的编号是递增的。

这就说明其实我们不用记录线段编号，只考虑 r 的大小就行了！！！

那此时我们按照左端点排序的顺序枚举线段，就可以把 t 滚掉了！！！

空间复杂度 O(nm)。

接着，你每次转移的时候考虑一下就是 r 和 R 只有一个会被修改。

你分别维护 dp 数组两维的前缀和，然后每次前缀和数组的修改量是 O(mk) 的，所以就 O(nmk) 了。