题解

思路

把线段按右端点排序。一个选择方案只需记录两种颜色中已经选择线段的最大右端点。选择颜色 1 的新线段时，颜色 2 的最大右端点必须严格小于新线段左端点；颜色 1 的记录则更新为当前右端点。

小范围枚举线段子集。中等范围显式维护所有可能的最大右端点。满分算法用两棵支持前缀加一、前缀最大值和单点更新的线段树优化。

做法

设状态 $(a,b)$ 表示两种颜色已选线段的最大右端点索引。令 row[a] 是固定 $a$ 时所有 $b$ 状态的最大答案，column[b] 对称定义。

处理颜色 1 的线段 $[l,r]$。所有满足第二种颜色右端点小于 $l$ 的状态都能选当前线段，因此 column 的对应前缀整体加一。新产生状态的颜色 1 索引是当前线段，故把该前缀的最大值写入 row[current]。颜色 2 完全对称。

排序后的右端点单调，可以二分找到合法前缀。两棵懒标记线段树完成前缀加、前缀最大值和单点取最大值。

复杂度

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。