CF1476F Lanterns
题目描述
有 $n$ 个灯笼拍成一排,第 $i$ 个灯笼具有 $p_i$ 的亮度。每个灯笼要么朝向左,照亮左边编号为 $[i - p_i,i - 1]$ 的灯笼,要么朝向右,照亮右边编号为 $[i + 1, i + p_i]$ 的灯笼。
寻找一种方案,为所有的灯笼确定朝向,使得每一个灯笼被至少一个其他灯笼照亮。
输入格式
第一行一个正整数表示数据组数 $t$。
每组数据包含两行。第一行为一个正整数 $n$,表示灯笼的个数。
第二行 $n$ 个整数 $p_i$,表示各个灯笼的亮度。
输出格式
对于每组数据,如果存在方案,在第一行输出字符串 $\texttt{YES}$,并在下一行给出一个长度为 $n$ 的仅由 $\texttt L$ 和 $\texttt R$ 组成的字符串,描述灯笼的方向。多解输出任意解。无解输出 $\texttt{NO}$。
说明/提示
$1\le t \le 1\times 10^4$。对于每组数据,有 $2\le n\le 3\times 10^5,0\le p_i\le n$。同一个测试点内保证 $\sum n\le 3\times 10^5$。