← 返回题目列表

AtCoder · past18_o

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 是整数。
  • 1\leq N,Q \leq 10^5
  • X_i 是偶数。
  • |X_i| \leq 10^9
  • X_i \neq X_j\ (i \neq j)
  • D_i is R or L.
  • 对于第一种查询,
    • x 是偶数。
    • |x| \leq 10^9
    • 在处理查询时,没有具有初始坐标的蚂蚁 x.
    • d is R or L.
  • 对于第二类的每个查询,
    • l 和 r 是整数。
    • 1 \leq l \leq r \leq M,其中 M 是 ant 的次数 1 与其他蚂蚁发生碰撞,从处理查询时的初始状态开始。

输入

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

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

在这里, \mathrm{query}_i 表示 i-th 查询,采用以下格式之一:

1 x d
2 l r

输出

如果有 T 第二类查询,打印 T 行。 在 i-th (1\leq i \leq T) 行,打印答案 i-第一个这样的查询。


示例输入 1

2 5
2 R
10 L
2 1 1
1 0 L
1 -2 R
2 1 2
2 2 2

示例输出 1

4
10
6

如果 Snuke 在处理查询之前在初始状态下打响指,蚂蚁的移动方式如下。

  • 时间 0,所有蚂蚁开始移动。 两只蚂蚁面朝左,面朝右。
  • 时间 4\ (:=t_1),蚂蚁 1 和 2 在坐标处碰撞 6。 现在两只蚂蚁面朝左、面朝右。

因此,答案 1-st 查询是 t_1=4.

如果 Snuke 在处理前三个查询的初始状态下打响指,蚂蚁的移动方式如下。 这里我们将添加的蚂蚁称为 2-nd 和 3-rd 查询蚂蚁 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.


示例输入 2

10 10
0 R
16 L
94 L
-96 R
-24 L
52 R
-10 L
-38 L
50 R
98 L
1 -66 L
2 2 3
1 48 L
1 34 R
2 2 2
1 8 L
2 2 3
2 2 3
1 62 L
2 1 3

示例输出 2

151
56
108
108
112