#5728. 「NOISG 2026 Final」Monkeys

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

题目描述

译自 NOISG 2026 Final T1. Monkeys

Monkeyland 是一个无限长的数轴，上面有 $n$ 只猴子，编号从 $1$ 到 $n$。第 $i$ 只猴子最初位于数轴上的位置 $p[i]$。多只猴子最初可能处于相同的位置。

Pan 可以用他的迷人法术让每只猴子移动！每只猴子的移动方式由一个长度为 $n$ 的字符串 $d$ 决定，其中每个字符要么是 $\texttt{L}$，要么是 $\texttt{R}$。设 $d$ 的第 $i$ 个字符为 $d[i]$。

一旦法术被施展，第 $i$ 只猴子将按以下规则移动：

• 如果 $d[i] = \texttt{L}$，它向左移动一个单位位置。
• 如果 $d[i] = \texttt{R}$，它向右移动一个单位位置。

Pan 每天会恰好施展一次法术。如果在任何一天（包括初始状态），有两只猴子处于相同的位置，它们就会成为朋友。若 Pan 连续 $k$ 天施展法术，请确定会有多少对猴子成为朋友。

输入格式

你的程序必须从标准输入读取数据。

第一行包含两个由空格分隔的整数 $n$ 和 $k$。

第二行包含 $n$ 个由空格分隔的整数 $p[1], p[2], \ldots, p[n]$。

第三行包含一个由 $n$ 个字符 $d[1], d[2], \ldots, d[n]$ 组成的字符串 $d$。

输出格式

你的程序必须输出到标准输出。

输出一个整数，表示成为朋友的猴子对数。

输出中应仅包含一个整数。请勿输出任何多余文本，如 Enter a number 或 The answer is。

样例 1

输入

2 1
1 3
RL

输出

1

共有 $n=2$ 只猴子，Pan 仅施展法术 $k=1$ 天。

在第一天，猴子 $1$ 从位置 $1$ 向右移动到位置 $2$，而猴子 $2$ 从位置 $3$ 向左移动到位置 $2$。由于它们在第一天结束时处于相同的位置，它们成为了朋友。因此，恰好有 $1$ 对猴子成为了朋友。

此样例满足子任务 $1, 3, 4, 5$ 和 $6$ 的限制。

样例 2

输入

5 67
1 2 3 4 5
RRRRR

输出

0

共有 $n=5$ 只猴子，Pan 连续 $k=67$ 天施展法术。

由于所有猴子的初始位置各不相同，且每天施展法术时每只猴子都向右移动一个单位，因此在任何一天都不会有两只猴子处于相同的位置。因此，没有猴子对能成为朋友。

此样例满足子任务 $2, 3, 4, 5$ 和 $6$ 的限制。

样例 3

输入

6 7
1 1 8 16 18 22
RRLRLL

输出

3

此样例满足子任务 $3, 4, 5$ 和 $6$ 的限制。

样例 4

输入

10 30
9 46 27 8 12 100 56 96 6 7
LRLRRLRRLR

输出

5

此样例满足子任务 $2,5$ 和 $6$ 的限制。

样例 5

输入

4 2
3 4 4 6
LLRL

输出

2

共有 $n=4$ 只猴子，Pan 连续 $k=2$ 天施展他的法术。

下面的每张图都将 Monkeyland 描绘为一个仅显示位置 $1$ 到 $6$ 的数轴。每只猴子上方的箭头指示了施展法术后它将移动的方向。

在第 $0$ 天，所有猴子的初始位置如下图所示。猴子 $2$ 和猴子 $3$ 已经处于位置 $4$，它们成为了朋友。

在第 $1$ 天施展法术后，所有猴子的位置如下图所示。猴子 $3$ 和猴子 $4$ 在位置 $5$ 相遇并成为了朋友。

在第 $2$ 天施展法术后，所有猴子的位置如下图所示。这一天没有两只猴子相遇。

此样例满足子任务 $3, 4, 5$ 和 $6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 200000$
• $1 \leq k \leq 10^9$
• 对于所有 $1 \leq i \leq n$，$1 \leq p[i] \leq 10^9$
• 对于所有 $1 \leq i \leq n$，$d[i]$ 为 L 或 R

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
$1$	$6$	$n=2$
$2$	$13$	$d[1]=d[2]=\cdots=d[n]$
$3$	$10$	$n, k \leq 200$
$4$	$22$	$n, k \leq 3000$
$5$	$18$	$n \leq 3000$
$6$	$31$	无附加限制