AT_past18_o.蟻の移動

有 $N$ 只蚂蚁，编号为 $1$ 到 $N$，它们位于一条数轴上，正方向向右。在初始状态下，第 $i$ 只蚂蚁位于初始坐标 $X_i$，朝向由字符 $D_i$ 描述。具体来说，$D_i=$ R 表示向右，$D_i=$ L 表示向左。保证 $X_1,X_2,\dots,X_N$ 是两两不同的偶数。

当 Snuke 打响指后，蚂蚁根据以下规则开始移动：

• 每只蚂蚁以每秒 $1$ 的速度朝自己面朝的方向前进。
• 每当两只蚂蚁到达同一坐标时，它们会同时调头并继续移动。此事件称为蚂蚁的碰撞。可以证明，三只或以上的蚂蚁绝不会在同一时刻到达同一坐标。

给定总共 $Q$ 个询问，每个询问有以下两种类型之一。按顺序处理它们。

• 1 x d：在初始状态中添加一只初始坐标为 $x$，朝向为 $d$ 的蚂蚁。这里保证 $x$ 为偶数，且与任意已存在蚂蚁的初始坐标都不同。
• 2 l r：若 Snuke 在时刻 $0$ 打响指，设 $t_1,t_2,\dots$ 为第 $1$ 只蚂蚁与其它蚂蚁碰撞的时刻，按时间顺序排列。计算 $t_l+t_{l+1}+\dots+t_r$ 并输出。保证 $l \leq r$，且第 $1$ 只蚂蚁与其它蚂蚁至少会碰撞 $r$ 次。

注意，第二类询问之间是相互独立的。也就是说，处理第二类询问不会实际改变蚂蚁的初始状态。

输入按如下格式从标准输入给出：

$N$ $Q$

$X_1$ $D_1$

$X_2$ $D_2$

$\vdots$

$X_N$ $D_N$

$\mathrm{query}_1$

$\mathrm{query}_2$

$\vdots$

$\mathrm{query}_Q$

其中，第 $i$ 个 $\mathrm{query}_i$ 为如下两种格式之一：

$1\ x\ d$

$2\ l\ r$

若有 $T$ 个第二类询问，共需输出 $T$ 行。对于第 $i$ 行 ($1\leq i \leq T$)，输出第 $i$ 个此类询问的答案。

样例说明 1

若 Snuke 在未处理任何询问时的初始状态下打响指，蚂蚁移动如下：

• 时刻 $0$，所有蚂蚁开始移动，二者分别朝右和朝左。
• 时刻 $4$（$t_1$），第 $1$ 只蚂蚁和第 $2$ 只蚂蚁在坐标 $6$ 处碰撞。此后两只蚂蚁分别朝左和朝右。

因此，第 $1$ 个询问的答案为 $t_1=4$。

若 Snuke 在处理完前三个询问后的初始状态下打响指，蚂蚁移动如下。新加入的蚂蚁，分别称为第 $3$ 只和第 $4$ 只蚂蚁。

• 时刻 $0$，所有蚂蚁开始移动，朝向分别为右、左、左、右。
• 时刻 $1$，第 $3$ 只和第 $4$ 只蚂蚁在坐标 $-1$ 处相遇。此后四只蚂蚁朝向分别为右、左、右、左。
• 时刻 $4$（$t_1$），第 $1$ 只和第 $2$ 只蚂蚁在坐标 $6$ 处相遇。此后四只蚂蚁朝向分别为左、右、右、左。
• 时刻 $6$（$t_2$），第 $1$ 只和第 $3$ 只蚂蚁在坐标 $4$ 处相遇。此后四只蚂蚁朝向分别为右、右、左、左。

因此，第 $4$ 个询问答案为 $t_1+t_2=10$，第 $5$ 个询问答案为 $t_2=6$。

数据范围

• $N$、$Q$ 为整数。
• $1\leq N,Q \leq 10^5$
• $X_i$ 为偶数。
• $|X_i| \leq 10^9$
• $X_i \neq X_j\ (i \neq j)$
• $D_i$ 取值为 R 或 L。
• 对于每个第 $1$ 类询问，
  • $x$ 为偶数。
  • $|x| \leq 10^9$
  • 在处理该询问时，没有蚂蚁的初始坐标为 $x$。
  • $d$ 取值为 R 或 L。
• 对于每个第 $2$ 类询问，
  • $l$、$r$ 为整数。
  • $1 \leq l \leq r \leq M$，其中 $M$ 是当前状态下第 $1$ 只蚂蚁与其它蚂蚁将发生碰撞的总次数。

由 ChatGPT 5 翻译