P15847 [NOISG 2026 Finals] 猴子 / Monkeys【暂无数据】

Monkeyland 是一条无限长的数轴，上面有 $n$ 只猴子，编号从 $1$ 到 $n$。第 $i$ 只猴子初始位于数轴上的位置 $p[i]$。允许多只猴子初始位于同一位置。 Pan 可以使用他的魔法让所有猴子移动！每只猴子的移动方式由一个长度为 $n$ 的字符串 $d$ 决定，其中每个字符是 `L` 或 `R`。令 $d$ 的第 $i$ 个字符为 $d[i]$。 一旦施放魔法，第 $i$ 只猴子将按如下规则移动： * 如果 $d[i] = \text{L}$，则它向左移动 **一个单位**。 * 如果 $d[i] = \text{R}$，则它向右移动 **一个单位**。 Pan 每天会恰好施放一次魔法。如果在任意一天（包括初始时）两只猴子位于同一位置，它们就会成为 **朋友**。如果 Pan 连续施法 $k$ 天，请确定将会成为朋友的 **猴子对** 的数量。

你的程序需要从标准输入读取数据。 输入的第一行包含两个由空格分隔的整数 $n$ 和 $k$。 输入的第二行包含 $n$ 个由空格分隔的整数 $p[1], p[2], \dots, p[n]$。 输入的第三行包含一个长度为 $n$ 的字符串 $d$，字符依次为 $d[1], d[2], \dots, d[n]$。

你的程序需要向标准输出写入数据。 输出一个整数，表示将会成为朋友的猴子对的数量。 输出应仅包含一个整数。不要输出任何额外的文本，例如 `Enter a number` 或 `The answer is`。

### 样例测试 #1 解释 共有 $n = 2$ 只猴子，Pan 只施法 $k = 1$ 天。 第一天，猴子 1 从位置 $1$ 向右移动到位置 $2$，而猴子 2 从位置 $3$ 向左移动到位置 $2$。由于它们在第一天结束时位于同一位置，它们成为了朋友。因此，恰好有 $1$ 对猴子成为了朋友。 ### 样例测试 #2 解释 共有 $n = 5$ 只猴子，Pan 连续施法 $k = 67$ 天。 由于所有猴子的初始位置互不相同，且每次施法时每只猴子都向右移动一个单位，因此在任何一天都不会有两只猴子位于同一位置。所以，没有猴子对能成为朋友。 ### 样例测试 #5 解释 共有 $n = 4$ 只猴子，Pan 连续施法 $k = 2$ 天。 下面的每张图都描绘了 Monkeyland 数轴的一部分，仅显示位置 $1$ 到 $6$。每只猴子上方的箭头表示它在施法后将移动的方向。 在第 $0$ 天，所有猴子的初始位置如下图所示。已经位于位置 $4$ 的猴子 $2$ 和猴子 $3$ 成为了朋友。 :::align{center}  ::: 在第 $1$ 天施法后，所有猴子的位置如下图所示。猴子 $3$ 和猴子 $4$ 在位置 $5$ 相遇并成为了朋友。 :::align{center}  ::: 在第 $2$ 天施法后，所有猴子的位置如下图所示。这一天没有猴子相遇。 :::align{center}  ::: 因此，总共有 $2$ 对猴子成为了朋友：猴子 $2$ 和 $3$，以及猴子 $3$ 和 $4$。 ### 子任务 对于所有测试用例，输入数据满足以下限制： * $1 \le n \le 200\,000$ * $1 \le k \le 10^9$ * 对于所有 $1 \le i \le n$，有 $1 \le p[i] \le 10^9$ * 对于所有 $1 \le i \le n$，$d[i]$ 是 `L` 或 `R` 你的程序将在满足以下限制的输入实例上进行测试： | 子任务 | 分数 | 额外约束条件 | |:------:|:----:|----------------------------------| | 0 | 0 | 样例测试用例 | | 1 | 6 | $n = 2$ | | 2 | 13 | $d[1] = d[2] = \cdots = d[n]$ | | 3 | 10 | $n, k \le 200$ | | 4 | 22 | $n, k \le 3000$ | | 5 | 18 | $n \le 3000$ | | 6 | 31 | 无额外约束 | 翻译由 DeepSeek V3.2 完成