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 翻译