题解

思路

把一种颜色的两个位置看成区间。只要某个颜色区间的两个端点都亮了，区间内部会全部点亮；因此区间 $A$ 内含有颜色 $B$ 的任一端点时，$A$ 可以传播到 $B$。

做法

建立颜色有向图：若 $B$ 的至少一个端点严格位于 $A$ 的两端之间，则连边 $A\to B$。点亮某个灯泡会立即点亮其同色灯泡，之后能点亮该颜色在图中可达的所有颜色。

缩点后是 DAG。每个入度为零的 SCC 至少需要选择一个初始灯泡；选择其中任意颜色的任一只灯泡都能激活整个 SCC，所以该 SCC 有 $2\times size$ 种选择。答案为源 SCC 数量，方案数是这些选择数的乘积。

区间不交叉时不存在由交叉产生的环，源点恰为没有被其他区间包含的最外层区间，每个有两种选择。小规模可以枚举初始灯泡集合并直接模拟闭包。

复杂度

简单版显式建图，时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。