P16368 [OOI 2026] March of the Sheep

Sasha 厌倦了沉重的城市生活，决定搬到乡下去。为了打发时间，他决定养羊。为此，他在村子里购置了一块矩形田地，可以表示为一个大小为 $n \times m$ 的网格，其中行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。 在他的田地上，Sasha 买了 $n$ 只羊，每只分配一整行。初始时，第 $i$ 只羊位于坐标为 $(i, a_i)$ 的格子（第 $i$ 行第 $a_i$ 列）。Sasha 发现羊只会按照以下规则水平移动： - 如果田地里只有一列，羊不移动。 - 初始时，第 $i$ 只羊位于格子 $(i, a_i)$，每只羊都有一个初始移动方向——向左或向右。不存在位于第一列且向左移动的羊，也不存在位于最后一列且向右移动的羊。 - 每一秒，如果一只羊向左移动，它就向左移动一列；否则向右移动一列。 - 如果移动后一只羊到达了第 $1$ 列且正在向左移动，或者到达了最后一列且正在向右移动，它将改变方向为相反方向。因此，羊永远不会离开田地的边界。 :::align{center}  这是一个羊移动的例子，初始时第一只羊在第 $1$ 列并向右移动，第二只羊在第 $3$ 列并向左移动。第一张图展示的是初始状态，第二张是经过一秒后，第三张是移动开始后 $2$ 秒，第四张是移动开始后 $3$ 秒。 ::: Sasha 不喜欢羊移动得如此混乱；他希望所有的羊都步调一致地移动。这意味着所有羊应该位于同一列并且具有相同的移动方向。为了实现这一点，Sasha 可以按以下方式对他的田地进行若干次（可能为零次）修剪： - 他选择一个时间 $t$（从羊初始移动开始经过了多少秒）以及修剪后田地将剩余的列数 $x$。 - 在时刻 $t$，所有羊必须严格位于 $n \times x$ 大小的田地内。这意味着对于任意 $i$ 从 $1$ 到 $n$，第 $i$ 只羊在时刻 $t$ 必须位于格子 $(i, y_i)$，其中 $1 \leq y_i \leq x$。否则，这样的田地修剪是不允许的。 - 在此操作之后，从时刻 $t$ 开始，田地的列数减少为 $x$。 - 所有位于最后一列且正在向右移动的羊将改变方向为相反方向。 修剪过程的详细例子在注释部分描述。 Sasha 想知道，通过若干次修剪田地，是否有可能实现让所有羊步调一致地移动。如果可能，Sasha 还想知道田地最多可以剩余多少列，以及具体如何实现。请帮助 Sasha 解决这个问题！

第一行包含一个整数 $T$（$1 \leq T \leq 3$）—— 一个参数，指示需要输出答案的哪些信息。详细描述见“输出格式”。 第二行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 200,000$，$2 \leq m \leq 10^9$）—— 田地的行数和列数。 第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq m$）—— 羊初始所在的列号。 第四行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $\mathtt{L}$、$\mathtt{R}$ 组成，其中第 $i$ 个字符为 $\mathtt{L}$ 表示第 $i$ 只羊初始向左移动，为 $\mathtt{R}$ 表示初始向右移动。保证没有位于第一列的羊向左移动，也没有位于第 $m$ 列的羊向右移动。

第一行，如果 Sasha 无法实现所有羊步调一致地移动，输出 "No"（不含引号）。否则，输出 "Yes"（不含引号）。 若 $T = 2$ 或 $T = 3$，则在第二行输出 Sasha 可以让田地剩余的最多列数，使得所有羊能够步调一致地移动。若 $T=1$，**则不应输出此行**。 若 $T = 3$，则在第三行输出一个整数 $q$（$0 \leq q \leq 10^6$）—— Sasha 需要修剪田地的次数。在接下来的 $q$ 行中，输出每次修剪的描述。 对于每次田地修剪的描述，在一行内输出两个整数 $t$ 和 $x$（$0 \leq t \leq 10^{18}$，$1 \leq x < m$），其中 $t$ 是 Sasha 需要修剪田地的时间（从羊最初开始移动算起），而 $x$ 是此次操作后田地剩余的列数。 这些操作必须按 $t$ 的非递减顺序输出。在每次后续的修剪中，$x$ 必须小于前一次的 $x$。 如果存在多种合适的修剪序列，输出任意一种均可。 可以证明，在给定的约束下，如果存在解，则一定存在解满足给定的限制。 当 $T = 1$ 或 $T = 2$ 时，不要输出修剪的描述。

### 样例解释 考虑第三个样例： 第零秒时羊的状态。 :::align{center}  ::: 第一秒时羊的状态。 :::align{center}  ::: 将田地修剪为 $4$ 格。 :::align{center}  ::: 第二秒时羊的状态。 :::align{center}  ::: ### 计分 本题的测试数据分为 10 组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过样例测试。**离线测试** 表示你提交的解答在该组上的测试结果将仅在比赛结束后公布。每组的最终得分等于你所有提交的解答中在该组测试上获得的最高分。 | 子任务编号 | 分数 | 附加限制 | < | < | 必过组别 | 备注 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | $T$ | $n$ | $m$ | | | | $0$ | $0$ | $--$ | $--$ | $--$ | $--$ | 题目中的样例。 | | $1$ | $8$ | $T \leq 1$ | $--$ | $--$ | $--$ | | | $2$ | $11$ | $T \leq 2$ | $n \leq 3$ | $m \leq 4$ | $--$ | | | $3$ | $9$ | $--$ | $n = 2$ | $--$ | $--$ | $a_1 = 1, a_2 = m$ | | $4$ | $12$ | $--$ | $n = 2$ | $m \leq 200,000$ | $--$ | | | $5$ | $8$ | $--$ | $n = 2$ | $--$ | $3, 4$ | | | $6$ | $14$ | $T \leq 2$ | $n \leq 1000$ | $m \leq 1000$ | $2$ | | | $7$ | $10$ | $T \leq 2$ | $--$ | $--$ | $1, 2, 6$ | | | $8$ | $9$ | $--$ | $--$ | | $--$ | 字符串 $s$ 仅包含字符 $\mathtt{R}$。 | | $9$ | $12$ | $--$ | $n \leq 1000$ | $m \leq 1000$ | $0, 2, 6$ | | | $10$ | $7$ | $--$ | $--$ | $--$ | $0$--$9$ | **离线测试。** | 翻译由 DeepSeek V4 Pro 完成