← 返回题目列表

AtCoder · abc376_f

I. 手环(硬)

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

注意:该问题与问题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-th (1 \leq i \leq Q) 指令由字符表示 H_i 和一个整数 T_i,含义如下:

  • 执行一定数量的操作(可能为零),以便您的左手(如果 H_i is L)或你的右手(如果 H_i is R) 正在持有部分 T_i。 在这里,你 可能 移动未指定的另一只手 H_i.

在本问题的设定和约束下,可以证明任何指令都是可以实现的。

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

约束

  • 3\leq N \leq 3000
  • 1\leq Q \leq 3000
  • H_i is L or R.
  • 1 \leq T_i \leq N
  • N, Q,和 T_i 是整数。

输入

输入由标准输入按以下格式给出:

N Q
H_1 T_1
H_2 T_2
\vdots
H_Q T_Q

输出

打印遵循所有说明所需的最少操作总数。


样本输入 1

6 3
R 4
L 5
R 5

示例输出 1

6

通过执行以下操作,您可以遵循所有 Q 按顺序说明。

  1. 将右手作为一部分移动 2 \rightarrow 3 \rightarrow 4 遵循第一条指令。
  2. 将左手作为一部分移动 1 \rightarrow 6 \rightarrow 5 遵循第二条指令。
  3. 将左手作为一部分移动 5 \rightarrow 6,然后将右手作为一部分移动 4 \rightarrow 5 遵循第三条指令。

在这种情况下,操作总数为 2+2+1+1=6,这是最小值。


示例输入 2

100 2
L 1
R 2

示例输出 2

0

在某些情况下,您可以按照说明进行操作,而无需执行任何操作。


示例输入 3

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

示例输出 3

58