分数: 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 xor2 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