E - 冒険者と一列のモンスター 解説 /

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

配点 : 466 点

問題文

高橋君は N 体のモンスターが一列に並んだダンジョンに挑みます。i 番目 (1 \leq i \leq N) のモンスターの強さは A_i です。モンスターの強さおよび高橋君の体力はいずれも 0 以上 C 以下の整数で表されます。

高橋君はこのダンジョンに対して Q 回の操作を順に行います。操作は次の 2 種類です。

  • 1 p x : p 番目のモンスターの強さを x に変更する。この変更は以降の操作すべてに反映される。
  • 2 l r d : 体力の初期値が d の状態で、l 番目から r 番目までのモンスターを順に相手にしたとき、倒せるモンスターの数を求める。この操作はモンスターの強さを変更しない。

操作 2 l r d で倒せるモンスターの数は、次の手順で決まります。

現在の体力を h とし、最初 h = d とします。

i = l, l+1, \dots, r の順に、i 番目のモンスター（現在の強さ A_i）について以下を行います：

  • h \geq A_i ならば、そのモンスターを倒し、h を h - A_i に更新する。
  • h < A_i ならば、そのモンスターは倒せず、h は変化しない。

いずれの場合も、次のモンスターに進みます。

すべてのモンスターを見終わったとき、倒したモンスターの合計数がこの操作の答えです。

各操作 2 について、答えを出力してください。

制約

  • 1 \leq N \leq 50000
  • 1 \leq C \leq 50
  • 1 \leq Q \leq 20000
  • 0 \leq A_i \leq C (1 \leq i \leq N)
  • 操作 1 p x について：1 \leq p \leq N, 0 \leq x \leq C
  • 操作 2 l r d について：1 \leq l \leq r \leq N, 0 \leq d \leq C
  • 入力はすべて整数である。

入力

N C Q
A_1 A_2 \dots A_N
query_1
query_2
\vdots
query_Q
  • 1 行目には、モンスターの数 N、強さと体力の上限 C、操作の回数 Q がスペース区切りで与えられる。
  • 2 行目には、初期状態での各モンスターの強さ A_1, A_2, \dots, A_N がスペース区切りで与えられる。
  • 続く Q 行には、各操作が 1 p x または 2 l r d の形式で 1 行ずつ与えられる。ここで query_j は j 番目の操作を表す。

出力

操作 2 が現れるたびに、その答えを 1 行に出力してください。

入力例 1

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

出力例 1

2
4
1
2

入力例 2

4 5 6
0 5 1 4
2 1 4 0
2 2 4 5
1 3 5
2 1 4 5
1 1 2
2 1 2 1

出力例 2

1
1
2
0

入力例 3

12 20 14
4 0 15 3 8 6 2 20 1 7 5 10
2 1 12 20
2 3 8 10
1 8 4
2 3 8 10
1 2 9
2 1 5 12
1 10 0
2 9 12 7
2 1 1 3
1 3 0
2 1 4 4
1 12 20
2 6 12 20
2 5 5 8

出力例 3

4
2
2
2
3
0
2
6
1

入力例 4

40 50 25
0 50 1 25 13 37 8 8 49 2 17 33 5 41 12 29 0 6 44 19 23 7 31 15 4 48 10 21 36 3 27 14 39 11 30 16 45 9 22 34
2 1 40 50
2 1 10 0
1 2 0
2 1 5 50
1 9 10
2 6 15 30
1 20 50
2 18 22 49
2 25 40 50
1 17 50
2 16 18 50
1 40 0
2 35 40 20
1 1 50
2 1 3 50
2 10 30 45
1 26 1
1 37 2
2 24 38 25
2 30 30 3
1 30 50
2 29 31 50
1 14 0
2 11 15 41
2 1 40 50

出力例 4

3
1
5
4
3
5
2
2
2
6
5
1
1
4
4

入力例 5

1 1 7
0
2 1 1 0
2 1 1 1
1 1 1
2 1 1 0
2 1 1 1
1 1 0
2 1 1 0

出力例 5

1
1
0
1
1

Score : 466 pts

Problem Statement

Takahashi challenges a dungeon where N monsters are lined up in a row. The strength of the i-th (1 \leq i \leq N) monster is A_i. Both the monsters' strengths and Takahashi's health are represented as integers between 0 and C, inclusive.

Takahashi performs Q operations on this dungeon in order. There are two types of operations:

  • 1 p x : Change the strength of the p-th monster to x. This change is reflected in all subsequent operations.
  • 2 l r d : Determine the number of monsters that can be defeated when facing monsters from the l-th to the r-th in order, starting with an initial health of d. This operation does not change the monsters' strengths.

The number of monsters defeated in operation 2 l r d is determined by the following procedure:

Let the current health be h, initially h = d.

For i = l, l+1, \dots, r in order, do the following for the i-th monster (with current strength A_i):

  • If h \geq A_i, defeat that monster and update h to h - A_i.
  • If h < A_i, that monster cannot be defeated, and h remains unchanged.

In either case, proceed to the next monster.

After all monsters have been processed, the total number of defeated monsters is the answer for this operation.

For each operation 2, output the answer.

Constraints

  • 1 \leq N \leq 50000
  • 1 \leq C \leq 50
  • 1 \leq Q \leq 20000
  • 0 \leq A_i \leq C (1 \leq i \leq N)
  • For operation 1 p x: 1 \leq p \leq N, 0 \leq x \leq C
  • For operation 2 l r d: 1 \leq l \leq r \leq N, 0 \leq d \leq C
  • All input values are integers.

Input

N C Q
A_1 A_2 \dots A_N
query_1
query_2
\vdots
query_Q
  • The first line contains the number of monsters N, the upper limit of strength and health C, and the number of operations Q, separated by spaces.
  • The second line contains the initial strengths of each monster A_1, A_2, \dots, A_N, separated by spaces.
  • The following Q lines each contain an operation in the format 1 p x or 2 l r d, one per line. Here query_j represents the j-th operation.

Output

Each time operation 2 appears, output the answer on a single line.

Sample Input 1

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

Sample Output 1

2
4
1
2

Sample Input 2

4 5 6
0 5 1 4
2 1 4 0
2 2 4 5
1 3 5
2 1 4 5
1 1 2
2 1 2 1

Sample Output 2

1
1
2
0

Sample Input 3

12 20 14
4 0 15 3 8 6 2 20 1 7 5 10
2 1 12 20
2 3 8 10
1 8 4
2 3 8 10
1 2 9
2 1 5 12
1 10 0
2 9 12 7
2 1 1 3
1 3 0
2 1 4 4
1 12 20
2 6 12 20
2 5 5 8

Sample Output 3

4
2
2
2
3
0
2
6
1

Sample Input 4

40 50 25
0 50 1 25 13 37 8 8 49 2 17 33 5 41 12 29 0 6 44 19 23 7 31 15 4 48 10 21 36 3 27 14 39 11 30 16 45 9 22 34
2 1 40 50
2 1 10 0
1 2 0
2 1 5 50
1 9 10
2 6 15 30
1 20 50
2 18 22 49
2 25 40 50
1 17 50
2 16 18 50
1 40 0
2 35 40 20
1 1 50
2 1 3 50
2 10 30 45
1 26 1
1 37 2
2 24 38 25
2 30 30 3
1 30 50
2 29 31 50
1 14 0
2 11 15 41
2 1 40 50

Sample Output 4

3
1
5
4
3
5
2
2
2
6
5
1
1
4
4

Sample Input 5

1 1 7
0
2 1 1 0
2 1 1 1
1 1 1
2 1 1 0
2 1 1 1
1 1 0
2 1 1 0

Sample Output 5

1
1
0
1
1