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$ 表示，含义如下：

执行若干次操作（可以为零次），使得你的左手（若 $H_i$ 为 $L$）或你的右手（若 $H_i$ 为 $R$）握住部分 $T_i$。 在这里，你可以移动由 $H_i$ 未指定的另一只手。

在本问题的设定和约束下，可以证明任意指令都是可实现的。 求遵循所有指令所需的最少操作总数。

输入格式

输入从标准输入按以下格式给出： $N$ $Q$ $H_1$ $T_1$ $H_2$ $T_2$ $\vdots$ $H_Q$ $T_Q$

输出格式

输出遵循所有指令所需的最少操作总数。

6 3
R 4
L 5
R 5

6

100 2
L 1
R 2

0

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

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$ 均为整数。 通过执行如下操作，你可以按顺序遵循所有 $Q$ 条指令。

将你的右手从部分 $2 \rightarrow 3 \rightarrow 4$ 移动以完成第一条指令。 将你的左手从部分 $1 \rightarrow 6 \rightarrow 5$ 移动以完成第二条指令。 将你的左手从部分 $5 \rightarrow 6$，然后将你的右手从部分 $4 \rightarrow 5$ 移动以完成第三条指令。

在这种情况下，总操作数为 $2+2+1+1=6$，这是最少的。
也有在不执行任何操作的情况下就能遵循指令的情况。

标签: AtCoder|abc376F

来源

AtCoder|abc376F