题解

思路

按照右端点处理线段，把一个合法选择唯一拆成若干连续的同色块；用上一同色块末尾的异色线段右端点刻画转移边界。

做法

一、同色子任务

若一组数据中的所有线段颜色相同，任意两条被选线段都不会违反限制。每条线段均可独立选择或不选，答案为 $2^n$。

二、枚举子集

当 $n\le20$ 时，可以枚举全部 $2^n$ 个子集。预处理每条线段与哪些异色线段重合；若子集中包含任意一对冲突线段，则该子集不合法。复杂度为 $O(2^n n)$。

三、按右端点建立状态

把线段按右端点从小到大排序。对每个已经处理的线段 $j$ 维护一个状态，状态颜色为 $c_j$，关键字为 $r_j$，权值记为 $v_j$。另外对两种颜色各建立一个关键字为 $0$、初始权值为 $1$ 的哨兵，表示此前没有选择异色线段。

处理线段 $i=[l_i,r_i]$，颜色为 $c_i$ 时，只考虑颜色 $c_i\oplus1$ 的状态。所有满足 $r_j<l_i$ 的状态都可以与线段 $i$ 衔接，因为闭区间在且仅在严格不等式成立时才不重合。令这些状态的权值和为 $f_i$，则：

1. 新增颜色 $c_i$、关键字 $r_i$、权值 $f_i$ 的状态；
2. 所有满足 $r_j<l_i$ 的异色状态权值乘 $2$，表示今后的方案可自由决定是否选择线段 $i$；
3. 把 $f_i$ 加入总答案。

初始总答案为 $1$，对应空集。

状态含义与正确性

固定一个非空合法方案，观察它按右端点排序后最后一段连续同色的被选线段。设这个同色块之前最后一条被选异色线段为 $j$；若不存在，就使用对应哨兵。块中每条线段的左端点都必须严格大于 $r_j$，反之满足该条件的同色线段可独立选择而不会与更早的异色线段相交。

当块中最后处理的被选线段为 $i$ 时，状态 $j$ 的权值已恰好为此前方案数乘上所有可自由选择同色线段产生的 $2$ 的幂，因此它对 $f_i$ 贡献一次。每个非空合法方案的最后同色块和其最后处理线段唯一，所以不会重计；上述条件也保证每个计入方案合法。因此转移完整且无重复。

四、复杂度优化

直接扫描全部异色状态即可得到 $O(n^2)$ 算法，足以通过 $n\le2000$ 的子任务。

满分算法对两种颜色分别按右端点离散化，并各维护一棵支持以下操作的线段树：

• 查询关键字小于 $l_i$ 的前缀权值和；
• 将这个前缀全部乘 $2$；
• 在关键字 $r_i$ 处加上新状态权值。

三种操作均为 $O(\log n)$。

注意区间是闭区间：应查询 $r_j<l_i$，不能误写成 $r_j\le l_i$。

复杂度

每个测试数据的总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$；所有测试数据合计时间复杂度为 $O(\sum n\log n)$。