O - Movement of Ants Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

1 から N までの番号が付けられた N 匹の蟻が数直線上に並んでいます。 この数直線上では右に行くほど座標が大きくなります。 初期状態において、蟻 i は初期座標 X_i におり、向いている向きは文字 D_i によって表されます。 具体的には、D_i= R のとき右を、D_i= L のとき左を向いています。 ここで、X_1,X_2,\dots,X_N はすべて偶数であり、互いに相異なることが保証されます。

すぬけくんが指を鳴らすと、蟻たちは以下の規則に従って動き始めます。

  • それぞれの蟻は、自分が向いている方向に向かって秒速 1 で数直線上を移動する。
  • 2 匹の蟻が同時にある座標に到達した場合は、それぞれの蟻が向きを反対方向に変えて移動を続ける。これを蟻の衝突とよぶ。 なお、3 匹以上の蟻が同時にある座標に到達することはないことが証明できる。

以下のいずれかの形式のクエリが合わせて Q 個与えられるので、順番に処理してください。

  • 1 x d : 初期座標が x、向いている向きが文字 d で表されるような蟻を初期状態に追加する。 ここで、x は偶数であり、既に存在するどの蟻の初期座標とも一致しないことが保証される。
  • 2 l r : 現在の初期状態において時刻 0 にすぬけくんが指を鳴らした場合に、蟻 1 と他の蟻との衝突が起こる時刻を早い順に t_1,t_2,\dots とする。 t_{l}+t_{l+1}+\dots +t_{r} を求め、出力する。 ただし、l \leq r、および蟻 1 と他の蟻との衝突は r 回以上起こることが保証される。

なお、2 種類目のクエリは独立であることに注意してください。 すなわち、2 種類目のクエリを処理することで、蟻たちの初期状態が変わることはありません。

制約

  • 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 と他の蟻との衝突が起こる回数

入力

入力は以下の形式で標準入力から与えられる。

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 番目のクエリを表し、以下のいずれかの形式である。

1 x d

2 l r

出力

2 種類目のクエリの数を T としたとき、T 行出力せよ。 i\ (1\leq i \leq T) 行目には、2 種類目のクエリのうち 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

クエリを処理する前の段階での初期状態においてすぬけくんが指を鳴らした場合、蟻たちは以下のように行動します。

  • 時刻 0 にすべての蟻が移動を始める。それぞれの蟻が向いている向きは右、左である。
  • 時刻 4\ (:=t_1) に座標 6 で蟻 1,2 が衝突する。それぞれの蟻が向いている向きは左、右になる。

よって、1 番目のクエリに対する答えは t_1=4 です。

3 番目のクエリまで処理した段階での初期状態においてすぬけくんが指を鳴らした場合、蟻たちは以下のように行動します。 ただし、2,3 番目のクエリで追加された蟻の番号をそれぞれ 3,4 とします。

  • 時刻 0 にすべての蟻が移動を始める。それぞれの蟻が向いている向きは右、左、左、右である。
  • 時刻 1 に座標 -1 で蟻 3,4 が衝突する。それぞれの蟻が向いている向きは右、左、右、左になる。
  • 時刻 4\ (:=t_1) に座標 6 で蟻 1,2 が衝突する。それぞれの蟻が向いている向きは左、右、右、左になる。
  • 時刻 6\ (:=t_2) に座標 4 で蟻 1,3 が衝突する。それぞれの蟻が向いている向きは右、右、左、左になる。

よって、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

Problem Statement

N ants numbered 1 through N are on a number line, whose positive direction points to the right. In the initial state, ant i is at the initial coordinate X_i and facing the direction described by a character D_i. Specifically, D_i= R means it is facing right, and D_i= L means it is facing left. Here, it is guaranteed that X_1,X_2,\dots, and X_N are pairwise distinct even numbers.

Once Snuke snaps his fingers, the ants starts moving according to the following rules.

  • Each ant moves at a speed of 1 per second in the direction it is facing.
  • Whenever two ants reach the same coordinate, they flip their directions and continue moving. This event is called a collision of ants. One can prove that three or more ants never reach the same coordinate at the same time.

You are given a total of Q queries, each of one of the following types. Process them in order.

  • 1 x d : Add an ant with initial coordinate x and initial direction d to the initial state. Here, it is guaranteed that x is even and does not coincide with the initial coordinate of any ant.
  • 2 l r : If Snuke snaps his fingers at time 0, let t_1,t_2,\dots be the times at which ant 1 collides with the other ants, listed in chronological order. Evaluate t_{l}+t_{l+1}+\dots +t_{r} and print it. It is guaranteed that l \leq r and ant 1 collides with the other ants at least r times.

Note that queries of the second type are independent. In other words, processing a query of the second type does not actually modify the initial states of the ants.

Constraints

  • N and Q are integers.
  • 1\leq N,Q \leq 10^5
  • X_i is even.
  • |X_i| \leq 10^9
  • X_i \neq X_j\ (i \neq j)
  • D_i is R or L.
  • For each query of the first kind,
    • x is even.
    • |x| \leq 10^9
    • At the point the query is processed, there is no ant with initial coordinate x.
    • d is R or L.
  • For each query of the second kind,
    • l and r are integers.
    • 1 \leq l \leq r \leq M, where M is the number of times ant 1 collides with the other ants, starting from the initial state at the point the query is processed.

Input

The input is given from Standard Input in the following format:

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

Here, \mathrm{query}_i denotes the i-th query and is of one of the following formats:

1 x d

2 l r

Output

If there are T queries of the second kind, print T lines. In the i-th (1\leq i \leq T) line, print the answer to the i-th such query.

Sample Input 1

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

Sample Output 1

4
10
6

If Snuke snaps his fingers in the initial state before the queries are processed, the ants move as follows.

  • At time 0, all the ants start moving. The two ants are facing right and left.
  • At time 4\ (:=t_1), ants 1 and 2 collide at coordinate 6. Now the two ants are facing left and right.

Thus, the answer to the 1-st query is t_1=4.

If Snuke snaps his fingers in the initial state where the first three queries are processed, the ants move as follows. Here we call the ants added by the 2-nd and 3-rd query ant 3 and ant 4, respectively.

  • At time 0, all the ants start moving. The four ants are facing right, left, left, and right.
  • At time 1, ants 3 and 4 collides at coordinate -1. Now, the four ants are facing right, left, right, and left.
  • At time 4\ (:=t_1), ants 1 and 2 collides at coordinate 6. Now, the four ants are facing left, right, right, and left.
  • At time 6\ (:=t_2), ants 1 and 3 collides at coordinate 4. Now, the four ants are facing right, right, left, and left.

Therefore, the answer to the 4-th query is t_1+t_2=10, and the answer to the 5-th query is t_2=6.

Sample Input 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

Sample Output 2

151
56
108
108
112