AT_abc376_f [ABC376F] Hands on Ring (Hard)

题目描述

注：本题与 B 题几乎相同，仅有正文中加粗部分及约束条件不同。

你正用双手握住一个环。这个环由 $N\ (N\geq 3)$ 个部件 $1,2,\dots,N$ 组成，部件 $i$ 与部件 $i+1$（$1\leq i\leq N-1$），以及部件 $1$ 与部件 $N$ 互为相邻。

最初，左手握住部件 $1$，右手握住部件 $2$。你可以在一次操作中执行以下动作：

• 将一只手移动到当前握住的部件的相邻部件之一，但前提是目标部件上没有另一只手。

下图展示了初始状态，以及从该状态出发可以进行和不能进行的操作示例。环上各部件的数字表示部件编号，标有 L 的圆圈表示左手，标有 R 的圆圈表示右手。

你需要依次按照给定的 $Q$ 条指示操作。第 $i\ (1\leq i\leq Q)$ 条指示由字符 $H_i$ 和整数 $T_i$ 表示，其含义如下：

• 通过若干次操作（可以为 $0$ 次），使得如果 $H_i$ 为 L，则左手，若为 R，则右手，握住部件 $T_i$。此时，可以移动未被 $H_i$ 指定的另一只手。

在本题的设定和约束下，可以证明任意指示都可以达成。

请你求出，为了依次完成所有指示，所需操作次数的最小总和。

输入格式

输入按以下格式从标准输入读入。

$N$ $Q$
$H_1$ $T_1$
$H_2$ $T_2$
$\vdots$
$H_Q$ $T_Q$

输出格式

请输出依次完成所有指示所需操作次数的最小总和。

输入输出样例 #1

输入 #1

6 3
R 4
L 5
R 5

输出 #1

6

输入输出样例 #2

输入 #2

100 2
L 1
R 2

输出 #2

0

输入输出样例 #3

输入 #3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

输出 #3

58

说明/提示

约束

• $3\leq N \leq 3000$
• $1\leq Q \leq 3000$
• $H_i$ 为 L 或 R
• $1\leq T_i\leq N$
• $N,Q,T_i$ 均为整数

样例解释 1

可以按如下方式操作，依次完成 $Q$ 条指示：

1. 右手依次移动到部件 $2\rightarrow 3\rightarrow 4$，完成第 1 条指示。
2. 左手依次移动到部件 $1\rightarrow 6\rightarrow 5$，完成第 2 条指示。
3. 左手移动到部件 $5\rightarrow 6$，然后右手移动到部件 $4\rightarrow 5$，完成第 3 条指示。
   此时操作总次数为 $2+2+1+1=6$，且这是最小值。

样例解释 2

有时无需进行任何操作即可完成指示。

由 ChatGPT 4.1 翻译