← 返回题目列表

AtCoder · awc0092_e

E. 冒险家和一排怪物

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥挑战地下城 N 怪兽排列成一排。的实力 i-th (1 \leq i \leq N) 怪物是 A_i。怪物的力量和高桥的生命值都以整数表示 0 和 C,包括在内。

高桥表演 Q 按顺序对该地下城进行操作。有两种类型的操作:

  • 1 p x : 改变强度 p-第一个怪兽 x。这一变化反映在所有后续操作中。
  • 2 l r d : 决定面对怪物时可以击败的怪物数量 l-第 r- 按顺序排列,从初始健康状况开始 d。此操作不会改变怪物的强度。

行动中击败的怪物数量 2 l r d is determined by the following procedure:

让当前的健康状况为 h,最初 h = d.

对于 i = l, l+1, \dots, r 按顺序执行以下操作 i- 第一个怪物(当前强度 A_i):

  • If h \geq A_i,击败该怪物并更新 h to h - A_i.
  • If h < A_i,那只怪兽不能被击败,并且 h 保持不变。

无论哪种情况,都继续处理下一个怪物。

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

对于每个操作 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
  • The first line contains the number of monsters N,体力和生命值上限 C,以及操作次数 Q,用空格分隔。
  • 第二行包含每个怪物的初始强度 A_1, A_2, \dots, A_N,用空格分隔。
  • The following Q lines each contain an operation in the format 1 p x or 2 l r d,每行一个。这里 query_j 代表 j-第次操作。

输出

每次操作 2 appears, output the answer on a single line.


样本输入 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