题解

先按树根坐标排序。每棵树最终占据的区间都包含自己的树根，因此这些区间如果互不相交，顺序也一定与树根顺序相同。

从左往右决定时，前面的树只会留下一个限制，已经占据的最右位置 $p$。当前树向左倒是否合法，只需看

这里必须严格大于，碰到端点也不合法。

能左倒时，直接左倒

左倒和保持不动的右端点都是 $x_i$，给后面的树留下的空间完全相同。但左倒能多清理一棵，所以没有理由选保持不动。

与右倒相比，左倒同样清理一棵，却占用更少的右侧空间，而且 L 的字典序更小。所以只要左倒合法，就可以直接选择 L。

这一步还可以用替换最优方案来说明。固定已经选好的前缀，取一个最优的后续方案，把当前树改成合法的左倒，不会挤到后面的树，也不会减少清理数。因此至少存在一个最优方案与这个选择一致。

不能左倒时，右倒会不会耽误后面

右倒必须满足 $x_i+R_i<x_{i+1}$，否则会碰到下一棵树的树根。这个树根无论下一棵向哪边倒、是否保持不动，都会被占据，所以越过它一定不合法。最后一棵没有右侧限制。

假设右倒合法。它可能挤到下一棵树向左倒所需的空间，这也是本题需要证明的地方。

取一个与当前已选前缀一致的最优方案。如果它把当前树留着，我们尝试改成右倒。

新占据的部分完全在下一棵树根左边，因此只可能影响下一棵的左倒。更后面的树，在原来的合法方案中也不能越过下一棵的树根，不会碰到当前树新增的部分。

若确实影响了下一棵左倒，就把下一棵改成保持不动。当前多清理一棵，下一棵少清理一棵，总数不变；下一棵的右端点仍是它的树根，不会继续影响更后面的决策。

因此总能找到一个当前选择右倒的最优方案。而在这些清理数相同的方案中，当前位置由 S 改成了更小的 R，第一次不同的位置已经更优，后面的字符不必再比较。

所以完整规则就是，能左倒选 L，否则能右倒选 R，都不行才选 S。

每一步都有一个最优方案可以采用当前选择，并且在不损失最优清理数的前提下选择了最小字符。依次做完，就同时得到了最大清理数和最小字典序。

实现时只维护右端点

选 L 或 S 后，让 $p=x_i$；选 R 后，让 $p=x_i+R_i$。初始 $p$ 设为足够小的数。

还可以检查一个始终成立的条件，每次处理树 $i$ 时，已有的 $p<x_i$。上一棵若右倒，已经检查过不能碰当前树根；否则上一棵的右端点就是它自己的树根。所以当前树保持不动始终合法，不需要再特判前面已经撞到了它。

排序耗时 $O(n\log n)$，之后扫描 $O(n)$，空间为 $O(n)$。输入未必有序，输出串按排序后的顺序排列。左右倒伏长度分别用 $L_i,R_i$，不能当成同一个长度。

三档部分分

$n\le12$ 的 20 分，可以枚举每棵树的 L/R/S，计算各自占据的闭区间，逐对检查相邻区间有没有接触。合法区间的顺序与树根顺序一致，相邻检查就足够。再按清理数、字典序挑出最优方案。时间 $O(n3^n+n\log n)$，空间 $O(n)$。

$n\le2000$ 的 15 分，可以增加一个“清理数量”的维度做 DP。若只求数量，记录前 $i$ 棵树清理 $j$ 棵时最小的右端点即可。但本题还要求字典序最小，不能只随便保留一个前驱。下面反过来做，方便从左到右恢复答案。

设 $f_{i,j}$ 表示：只安排第 $i$ 到第 $n$ 棵树，恰好清理 $j$ 棵，在所有合法方案中，第一棵占用区间的左端点最大能是多少。无解记为 $-\infty$，空后缀取 $f_{n+1,0}=+\infty$，其余数量无解。

枚举第 $i$ 棵的决策，它占据 $[l,r]$，清理数为 $c\in\{0,1\}$。如果 $r<f_{i+1,j-c}$，就存在一种后缀方案不会碰到它，可以用 $l$ 更新 $f_{i,j}$ 的最大值。反过来，任何合法安排的后缀左端点一定大于 $r$，所以这个条件也不会漏掉方案。

找到最大的可行数量后，从左往右恢复。已确定的部分占到 $p$，还要清理 $j$ 棵时，按 L/R/S 的顺序尝试，取第一个同时满足 $l>p$ 和 $r<f_{i+1,j-c}$ 的决策。这两个条件分别保证不碰前面，以及后面仍然能完成目标数量，因此得到的就是最优数量下字典序最小的方案。时间、空间均为 $O(n^2)$；它也能通过子任务 1，合计 35 分。

25 分的性质保证，对所有非最后的树都有 $x_i+R_i\ge x_{i+1}$。这些树根本不能右倒，只剩左倒和不动，而这两种选择的右端点相同。于是每棵内部树能否左倒只取决于 $x_i-L_i>x_{i-1}$，各自独立决定。第一棵总能左倒；最后一棵能左倒就左倒，否则右倒。排序后线性扫描，时间 $O(n\log n)$、空间 $O(n)$。

这个性质省去了上面关于右倒影响下一棵的交换论证。与小规模枚举组合可以保证 45 分；与上述 $O(n^2)$ DP 组合，可以得到 60 分。

DP 也能拿满分

如果发现前后两棵树是否冲突只取决于它们各自的 L/R/S，就不必再记录清理数量。设 $g_{i,c}$ 为第 $i$ 棵固定采用决策 $c$ 时，后缀最多能清理的数量。枚举下一棵的三种决策 $d$，只在当前右端点严格小于下一棵左端点时转移，取 $g_{i+1,d}$ 的最大值并加上当前的贡献。边界是最后一棵选 L/R 得 1，选 S 得 0；不存在合法后续的状态记为负无穷。

恢复方案时，同样从左往右按 L/R/S 尝试，要求不碰前面，且 $g_{i,c}$ 等于剩余的最优清理数。相邻区间都不相交就能保证全局合法，所以三种状态足够。排序后只有 $O(n)$ 次转移，总时间 $O(n\log n)$，空间 $O(n)$，可以通过全部子任务。这是另一种完整解法，不依赖贪心的交换论证。

参考代码

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;
struct Tree { ll x, left, right; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Tree> a(n);
    for (auto &v : a) cin >> v.x >> v.left >> v.right;
    sort(a.begin(), a.end(), [](const Tree &u, const Tree &v) { return u.x < v.x; });
    ll occupied = -(1LL << 60);
    string plan;
    plan.reserve(n);
    int answer = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i].x - a[i].left > occupied) {
            plan += 'L';
            occupied = a[i].x;
            ++answer;
        } else if (i + 1 == n || a[i].x + a[i].right < a[i + 1].x) {
            plan += 'R';
            occupied = a[i].x + a[i].right;
            ++answer;
        } else {
            plan += 'S';
            occupied = a[i].x;
        }
    }
    cout << answer << '\n' << plan << '\n';
}