Statement

nn 个灯笼排成一排，第 ii 个灯笼具有 pip_i​ 的亮度。每个灯笼要么朝向左，照亮左边编号为 [i−pi​,i−1][i − p_i​, i − 1] 的灯笼；要么朝向右，照亮右边编号为 [i+1,i+pi​][i + 1, i + p_i​] 的灯笼。

请你为所有的灯笼确定朝向，使得每一个灯笼至少被另外一个灯笼照亮，或判断无解。

数据范围：n≤3×105n \le 3 \times 10^5。

Solution

神仙 DP。

把可行性问题转化为最优性问题，设 f(i)f(i) 表示前 ii 个灯笼能覆盖的最长前缀。

转移考虑第 ii 个灯笼的朝向。如果向右，那么

f(i)={f(i−1),f(i−1)<imax⁡{f(i−1),i+pi},f(i−1)≥if(i) = \begin{cases} f(i - 1), &f(i - 1) < i \\ \max\{f(i - 1), i + p_i\}, &f(i - 1) \ge i \end{cases}

如果向左，那么找到最小的 jj 满足 f(j)≥i−pi−1f(j) \ge i - p_i - 1，那么

f(i)=max⁡{f(j),max⁡k=j+1i−1{k+pk}}f(i) = \max\left\{f(j), \max_{k = j + 1} ^ {i - 1}\{k + p_k\}\right\}

时间复杂度 O(nlog⁡n)O(n \log n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using std::max; using std::min; const int N = 3e5 + 7, LogN = 19;
struct ST{
    int f[N][LogN], lg2[N];
    void init(int n) {
        lg2[0] = -1; for(int i = 1; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
        for(int k = 1; k <= lg2[n]; k++)
            for(int i = 1; i + (1 << k) - 1 <= n; i++)
                f[i][k] = max(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
    }
    int query(int l, int r) {
        if(l > r) return 0;
        int k = lg2[r - l + 1];
        return max(f[l][k], f[r - (1 << k) + 1][k]);
    }
} st;
struct BIT{
    int n, c[N];
    void init(int nn) { n = nn; for(int i = 0; i <= n + 1; i++) c[i] = n + 1; }
    void add(int x, int v) { x++; while(x) c[x] = min(c[x], v), x -= x & -x; }
    int query(int x) {
        int s = n + 1; x = max(x, 0) + 1;
        while(x <= n + 1) s = min(s, c[x]), x += x & -x;
        return s;
    }
} bit;
int n, p[N]; std::pair<int, int> f[N]; char ans[N];
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", p + i), st.f[i][0] = p[i] + i;
    st.init(n), bit.init(n), f[0] = {0, -1}, bit.add(0, 0);
    for(int i = 1; i <= n; i++) {
        f[i] = {max(f[i - 1].first < i ? 0 : i + p[i], f[i - 1].first), -1};
        int j = bit.query(i - p[i] - 1);
        if(j <= n) {
            int nw = max(f[j].first, max(st.query(j + 1, i - 1), i - 1));
            f[i] = max(f[i], {nw, j});
        }
        bit.add(f[i].first, i);
    }
    if(f[n].first < n) return puts("NO"), void();
    puts("YES"); int pos = n;
    while(pos > 0)
        if(~f[pos].second) {
            for(int i = f[pos].second + 1; i < pos; i++) ans[i] = 'R';
            ans[pos] = 'L', pos = f[pos].second;
        } else ans[pos] = 'R', pos--;
    ans[n + 1] = 0, printf("%s\n", ans + 1);
}
int main() {
    int T; scanf("%d", &T); while(T--) solve();
    return 0;
}