题解

思路

依次处理灯笼。令 $dp_i$ 表示只决定前 $i$ 个灯笼的方向后，可以确认已经被照亮的最远位置。尚未被确认照亮的末尾若干灯笼暂时都朝右，它们可以在之后被某个朝左的灯笼照亮。

记

处理第 $i$ 个灯笼时有两类转移。

第一类令它朝右。如果此前已有 $dp_{i-1}\ge i$，说明第 $i$ 个灯笼已经被照亮，它朝右后可以把最远照亮位置更新为 $\max(dp_{i-1},r_i)$。也可以暂时不确认它及其右侧贡献，保留 $dp_i=dp_{i-1}$，等待后面的朝左灯笼收束这一段。

第二类令它朝左。设某个旧状态为 $m$，并让第 $m+1$ 到第 $i-1$ 个灯笼全部朝右、第 $i$ 个灯笼朝左。只要 $dp_m\ge l_i-1$，第 $i$ 个灯笼就能接上此前已经覆盖的前缀，并照亮这一整段的左侧。新状态为

在所有满足 $dp_m\ge l_i-1$ 的状态中，最小的 $m$ 一定最优，因为它包含的朝右灯笼区间最大。记录每次转移的来源即可反向恢复方向字符串。

直接枚举 $m$ 可以得到平方算法。满分算法需要维护两种查询：

• 按 $dp_m$ 的值查询所有 $dp_m\ge l_i-1$ 中最小的下标 $m$；
• 查询一段连续灯笼的 $r_q$ 最大值。

分别使用维护区间最小值和区间最大值的线段树，就能在对数时间完成一次转移。

做法

初始化 $dp_0=0$。把每个已经得到的状态 $i$ 按照键 $dp_i$ 插入第一棵线段树，叶子保存该键对应的最小状态下标；在后缀区间 $[l_i-1,n]$ 查询最小值，即得到第二类转移所需的最小 $m$。

第二棵线段树预先存储所有 $r_i$，用于查询 $m+1$ 到 $i-1$ 的最大右端点。然后依次比较朝左成段转移、已被照亮后朝右转移和暂缓确认转移，保留使 $dp_i$ 最大的来源。

若最终 $dp_n=n$，则所有位置都能被照亮。根据来源数组从 $n$ 反向恢复：普通转移把当前灯笼设为 R；成段转移把末端设为 L，中间灯笼设为 R，再跳回旧状态。若 $dp_n\ne n$，则不存在合法方案。

上述转移枚举了最后一个朝左灯笼收束未确认后缀的位置，因此不会漏掉任何合法方案；每个得到的状态也对应一份可恢复的合法前缀方案，所以算法同时具有充分性和必要性。

复杂度

设所有数据组的灯笼总数为 $N$。时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。