1002. 小笨蛋

题目描述

小笨蛋在数轴上 [0,n] 之间的整点移动，从 0 出发、在 0 结束，每次可以选择向左（操作 L，并在移动序列末尾追加一个 L）或向右（操作 R，并在移动序列末尾追加一个 R）移动一格。

允许在 0 处操作 L，在 n 处操作 R；如果在 0 向左、在 n 向右，则小笨蛋将留在原地。

给定数组 $c_0,c_1,...,c_n$，其中 $c_i$ 表示小笨蛋到达坐标 i 的次数。初始站在 0 的这一次不计入到达次数，只统计每次移动完成后的所在坐标。保证初始及任意一次修改后均有 $c_n>0$。

小笨蛋的计划经常发生变化。接下来会有 $q$ 次修改，每次修改给定四个整数 $L,R,Delta,opt$：

• 将区间 $[L,R]$ 内的所有 $c_i$ 同时增加 $Delta$。
• 询问当前状态下，是否能构造出合法的移动序列。
• 如果能，并且 opt=1，请额外输出字典序最小的左右移动序列。

输入格式

第一行包含一个整数 $T$，表示测试用例组数。

对于每组测试用例：

第一行包含两个整数 $n,q$。

第二行包含 $n+1$ 个整数，表示初始的 $c_0,c_1,...,c_n$。

接下来 $q$ 行，每行四个整数 $L,R,Delta,opt$，表示一次修改与询问。

• $1 <= T <= 10$
• $1 <= n <= 2 * 10^5$
• $1 <= q <= 2 * 10^6$
• $0 <= L <= R <= n$
• $-10^6 <= Delta <= 10^6$
• 初始 $1 <= c_i <= 10^6$
• 保证初始及任意一次修改后均有 $c_n>0$
• 对每组测试用例，保证所有 opt=1 查询输出序列的长度总和不超过 $2 * 10^6$

输出格式

对于每次修改，如果当前状态有解，先输出一行 Yes。若 opt=1，则在下一行输出对应的字典序最小序列。

如果当前状态无解，仅输出一行 No。

样例输入

1
1 4
1 1
0 0 0 1
0 1 1 1
0 0 -1 0
1 1 2 1

样例输出

Yes
RL
Yes
LRRL
Yes
Yes
RRRRL

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1002