D - 分岐する棚の整理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、位置 1 から位置 M までの整数座標が付いた一直線の棚に、N 個の置物を配置しました。

i 番目の置物 (1 \leq i \leq N) の初期位置は A_i です。複数の置物が同じ位置にあっても構いません。また、置物同士は互いに干渉しません。

この初期配置を状態 0 と呼びます。各状態は、棚の上に残っている置物の集合と、それぞれの位置の情報を保持しています。

これから Q 個の新しい状態を番号 1, 2, \ldots, Q の順に作ります。

状態 j (j = 1, 2, \ldots, Q) は、以下の手順で作られます。

  1. すでに存在する状態 P_j (0 \leq P_j \leq j-1) の内容（棚の上に残っている置物とその位置）をコピーして、新しい状態 j の初期内容とする。
  2. 状態 j に対して次の操作を 1 回だけ 行う。
  • C_j が L のとき：状態 j の棚の上にあるすべての置物の位置を D_j だけ減らす（左に D_j スライドさせる）。
  • C_j が R のとき：状態 j の棚の上にあるすべての置物の位置を D_j だけ増やす（右に D_j スライドさせる）。
  • この結果、位置が 1 未満または M より大きくなった置物は棚から落下し、状態 j から取り除かれる。

コピーにより新しい状態を作っても、コピー元の状態は一切変化しません。

なお、コピー元の状態番号 P_j の選び方により、状態 0 を根とする木構造が形成されます。

各 j = 1, 2, \ldots, Q について、状態 j において棚から落下した置物の個数（すなわち N から状態 j に残っている置物の個数を引いた値）を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq M (1 \leq i \leq N)
  • 0 \leq P_j \leq j - 1 (1 \leq j \leq Q)
  • C_j は L または R (1 \leq j \leq Q)
  • 1 \leq D_j \leq 10^9 (1 \leq j \leq Q)
  • 入力はすべて整数（C_j を除く）

入力

N M Q
A_1 A_2 \cdots A_N
P_1 C_1 D_1
P_2 C_2 D_2
\vdots
P_Q C_Q D_Q
  • 1 行目には、置物の個数 N、棚の右端の位置 M、作る状態の個数 Q が、スペース区切りで与えられる。
  • 2 行目には、各置物の初期位置 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目から Q 行にわたって、新しい状態の作り方が与えられる。
  • 2 + j 行目には、状態 j のコピー元の状態番号 P_j、移動方向 C_j、移動量 D_j が、スペース区切りで与えられる。

出力

Q 行出力せよ。

j 行目には、状態 j において棚から落下した置物の個数（N から状態 j に残っている置物の個数を引いた値）を整数で出力せよ。

入力例 1

5 10 4
1 3 5 8 10
0 R 2
0 L 1
1 L 4
2 R 10

出力例 1

1
1
2
5

入力例 2

6 7 6
2 2 4 6 7 7
0 L 1
0 R 1
1 R 3
2 L 5
3 L 2
5 R 10

出力例 2

0
2
3
5
3
6

入力例 3

15 100 12
1 5 10 20 20 35 50 65 70 80 90 95 100 42 58
0 R 10
0 L 15
1 R 40
1 L 5
2 R 60
2 L 10
3 L 30
4 R 25
5 R 1
6 L 1
8 L 70
10 R 90

出力例 3

2
3
7
2
10
5
7
4
10
5
10
14

入力例 4

30 1000000000 25
1 2 3 100 1000 100000 123456789 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 999999999 1000000000 42 4242 424242 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998
0 R 1
0 L 1
1 R 999999998
1 L 50
2 R 123456789
2 L 999999999
3 L 500000000
3 R 2
4 R 1000
4 L 1000
5 R 700000000
5 L 200000000
6 R 1
7 L 1
8 R 400000000
9 L 400000000
10 R 600000000
11 L 600000000
12 R 333333333
13 L 333333333
14 R 999999999
15 L 999999999
16 R 123
20 L 456
24 R 789

出力例 4

1
1
29
5
7
30
29
30
7
7
20
15
30
29
30
18
20
20
17
30
30
30
18
30
30

入力例 5

1 1 1
1
0 R 1000000000

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi has placed N figurines on a straight shelf with integer coordinates from position 1 to position M.

The initial position of the i-th figurine (1 \leq i \leq N) is A_i. Multiple figurines may be at the same position. Also, figurines do not interfere with each other.

This initial arrangement is called state 0. Each state holds the information about the set of figurines remaining on the shelf and their respective positions.

We will create Q new states, numbered 1, 2, \ldots, Q, in order.

State j (j = 1, 2, \ldots, Q) is created by the following procedure:

  1. Copy the contents of an already existing state P_j (0 \leq P_j \leq j-1) (the figurines remaining on the shelf and their positions) to use as the initial contents of the new state j.
  2. Perform the following operation exactly once on state j:
  • If C_j is L: Decrease the position of every figurine on the shelf in state j by D_j (slide them D_j to the left).
  • If C_j is R: Increase the position of every figurine on the shelf in state j by D_j (slide them D_j to the right).
  • As a result, any figurine whose position becomes less than 1 or greater than M falls off the shelf and is removed from state j.

Creating a new state by copying does not change the source state in any way.

Note that due to the way the source state number P_j is chosen, a tree structure rooted at state 0 is formed.

For each j = 1, 2, \ldots, Q, determine the number of figurines that have fallen off the shelf in state j (that is, the value of N minus the number of figurines remaining in state j).

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq M (1 \leq i \leq N)
  • 0 \leq P_j \leq j - 1 (1 \leq j \leq Q)
  • C_j is L or R (1 \leq j \leq Q)
  • 1 \leq D_j \leq 10^9 (1 \leq j \leq Q)
  • All inputs are integers (except for C_j)

Input

N M Q
A_1 A_2 \cdots A_N
P_1 C_1 D_1
P_2 C_2 D_2
\vdots
P_Q C_Q D_Q
  • The first line contains the number of figurines N, the position of the right end of the shelf M, and the number of states to create Q, separated by spaces.
  • The second line contains the initial positions of the figurines A_1, A_2, \ldots, A_N, separated by spaces.
  • The following Q lines describe how to create the new states.
  • The (2 + j)-th line contains the source state number P_j for state j, the direction of movement C_j, and the amount of movement D_j, separated by spaces.

Output

Output Q lines.

On the j-th line, output the number of figurines that have fallen off the shelf in state j (the value of N minus the number of figurines remaining in state j) as an integer.

Sample Input 1

5 10 4
1 3 5 8 10
0 R 2
0 L 1
1 L 4
2 R 10

Sample Output 1

1
1
2
5

Sample Input 2

6 7 6
2 2 4 6 7 7
0 L 1
0 R 1
1 R 3
2 L 5
3 L 2
5 R 10

Sample Output 2

0
2
3
5
3
6

Sample Input 3

15 100 12
1 5 10 20 20 35 50 65 70 80 90 95 100 42 58
0 R 10
0 L 15
1 R 40
1 L 5
2 R 60
2 L 10
3 L 30
4 R 25
5 R 1
6 L 1
8 L 70
10 R 90

Sample Output 3

2
3
7
2
10
5
7
4
10
5
10
14

Sample Input 4

30 1000000000 25
1 2 3 100 1000 100000 123456789 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 999999999 1000000000 42 4242 424242 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998
0 R 1
0 L 1
1 R 999999998
1 L 50
2 R 123456789
2 L 999999999
3 L 500000000
3 R 2
4 R 1000
4 L 1000
5 R 700000000
5 L 200000000
6 R 1
7 L 1
8 R 400000000
9 L 400000000
10 R 600000000
11 L 600000000
12 R 333333333
13 L 333333333
14 R 999999999
15 L 999999999
16 R 123
20 L 456
24 R 789

Sample Output 4

1
1
29
5
7
30
29
30
7
7
20
15
30
29
30
18
20
20
17
30
30
30
18
30
30

Sample Input 5

1 1 1
1
0 R 1000000000

Sample Output 5

1