#5738. 「OOI 2026 Day2」羊群大游行

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day2 T2 「Марш овец」 / 「March of the Sheep」。

萨沙厌倦了繁重的城市生活，决定搬到乡下。为了给日常生活找点乐子，他决定开始养羊。为此，他在村里买下了一块矩形区域，可以将其看作一个 $n \times m$ 的网格。网格的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。

萨沙为这块地买了 $n$ 只羊，并为每只羊分配了专门的一行。最初，第 $i$ 只羊被放置在坐标为 $(i, a_i)$ 的格子中（即第 $i$ 行第 $a_i$ 列）。萨沙发现，羊只会在水平方向上移动，并遵循以下规则：

• 若区域内只有一列，则羊不动。
• 最初，第 $i$ 只羊位于格子 $(i, a_i)$，且每只羊都有一个初始移动方向——向左或向右。保证不存在位于第一列且向左移动的羊，也不存在位于最后一列且向右移动的羊。
• 每过一秒，每只羊都会移动一列：若向左移动则移动到左侧一列，若向右移动则移动到右侧一列。
• 若移动后羊处于第一列且向左移动，或者处于最后一列且向右移动，它就会反转移动方向。这样，羊永远不会离开区域边界。

萨沙不喜欢羊群如此杂乱无章地移动，他希望所有羊的移动步调一致。这意味着所有的羊必须处于同一列，并且具有相同的移动方向。为了实现这一目标，萨沙可以对区域进行若干次（可能为零次）如下的“裁剪”操作：

• 他选择一个时间点 $t$（从羊群开始运动起经过的秒数）以及裁剪后区域保留的列数 $x$。
• 在时间点 $t$，所有羊必须严格位于大小为 $n \times x$ 的区域内。这意味着对于任意 $1 \le i \le n$，第 $i$ 只羊在时间 $t$ 必须位于格子 $(i, y_i)$，其中 $1 \le y_i \le x$。否则，该裁剪操作是不可行的。
• 该操作执行后，从时间 $t$ 开始，区域的列数减少为 $x$。
• 操作后，任何位于最后一列（第 $x$ 列）且向右移动的羊，都会立即反转移动方向。

裁剪过程的详细示例请参见样例说明。

萨沙首先想知道，是否可以通过多次裁剪，使得所有羊的移动步调一致。若可行，他想知道区域最后能保留的最大列数是多少，以及具体该如何操作。请帮萨沙解决这个问题！

输入格式

第一行包含一个整数 $T$ $(1 \le T \le 3)$，该参数表示需要输出哪种详细程度的答案。具体说明见「输出格式」。

第二行包含两个整数 $n$ 和 $m$ $(2 \le n \le 200000, 2 \le m \le 10^9)$，分别表示区域的行数和列数。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le m)$，表示每只羊初始所在的列号。

第四行包含一个长度为 $n$ 的字符串 $s$，由字符 L 和 R 组成。若第 $i$ 个字符为 L，则第 $i$ 只羊初始向左移动；若为 R，则初始向右移动。保证第一列的羊不会向左移，最后一列的羊不会向右移。

输出格式

第一行输出，若萨沙无法使羊群步调一致，则输出 No；否则输出 Yes。

若 $T=2$ 或 $T=3$，则在第二行输出萨沙在保证羊群步调一致的前提下，区域能保留的最大列数。若 $T=1$，则无需输出此行。

若 $T=3$，则在第三行输出一个整数 $q$ $(0 \le q \le 10^6)$，表示萨沙需要裁剪区域的次数。接下来的 $q$ 行输出裁剪操作的描述。

每个操作描述包含两个整数 $t$ 和 $x$ $(0 \le t \le 10^{18}, 1 \le x < m)$，其中 $t$ 是萨沙进行裁剪的时间点（从最初运动开始计），$x$ 是操作后区域保留的列数。

操作必须按 $t$ 的非递减顺序输出。在连续的裁剪操作中，$x$ 必须比前一次操作的值更小。

若有多种满足条件的裁剪序列，输出其中任意一种即可。

可以证明，在给定的限制条件下，若存在答案，则一定存在满足上述输出限制的答案。

若 $T=1$ 或 $T=2$，则无需输出裁剪操作的具体描述。

样例 1

输入

3
2 3
1 3
RL

输出

Yes
2
1
3 2

样例 2

输入

3
2 3
1 2
RL

输出

No

样例 3

输入

3
3 5
1 3 5
RRL

输出

Yes
3
2
1 4
2 3

$0$ 秒时羊群的状态：

图片下载失败URL：https://img.loj.ac.cn/2026/05/17/adb3e7a6c39e0.svg

$1$ 秒时羊群的状态：

图片下载失败URL：https://img.loj.ac.cn/2026/05/17/83a86f594d24c.svg

此时将区域裁剪至 $4$ 列：

图片下载失败URL：https://img.loj.ac.cn/2026/05/17/e90c1fd7e9651.svg

$2$ 秒时羊群的状态：

此时所有羊位置如下：

图片下载失败URL：https://img.loj.ac.cn/2026/05/17/7795eb19a4b71.svg

再次将区域裁剪至 $3$ 列：

此时所有羊都在第 $3$ 列且由于都在边界并试图（或已经）向右，最终方向都会统一。

最终状态：

图片下载失败URL：https://img.loj.ac.cn/2026/05/17/7f38096a623f9.svg

所有羊步调一致。

样例 4

输入

2
3 5
1 3 5
RRL

输出

Yes
3

样例 5

输入

1
3 5
1 3 5
RRL

输出

Yes

样例 6

输入

3
3 7
3 3 5
RRL

输出

Yes
4
3
0 6
0 5
1 4

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$T$ 限制	$n$ 限制	$m$ 限制	附加限制	子任务依赖
$1$	$8$	$T \le 1$	-	-	-
$2$	$11$	$T \le 2$	$n \le 3$	$m \le 4$		-
$3$	$9$	-	$n = 2$	-	$a_1 = 1, a_2 = m$
$4$	$12$			$m \le 200000$	-
$5$	$8$			-	-	$3, 4$
$6$	$14$	$T \le 2$	$n \le 1000$	$m \le 1000$	-	$2$
$7$	$10$		-	-		$1, 2, 6$
$8$	$9$	-			字符串 $s$ 仅含 R	-
$9$	$12$		$n \le 1000$	$m \le 1000$	-	$0, 2, 6$
$10$	$7$		-	-		$0 - 9$