← 返回题目列表

AtCoder · pakencamp_2022_day1_h

H. 攻击生存

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

配点 : 400 点

問題文

hiikunZ 你是智力问答比赛的组织者,但你不擅长管理分数。因此,我决定为您编写一个程序来管理“攻击生存”规则中的分数。编写一个程序来解决以下问题。

问答比赛 N 参与者正在参与, 它们的编号最大为 1 减去 N 。每个参与者都有一个参数,称为“体力”。一开始,参与者 i 的体力是 A_i 。和 Q 次, 发生 2 类型的事件。

  • 1 x y : 参加者 x 被授予 正确回答 y 问题。随后,与会人员 x 以外的健康状况 0 所有参与者的健康状况大于 错误回答 y 减少。
  • 2 x y : 参加者 x 被授予 正确回答 y 问题。随后,与会人员 x 的体力为 y 减少。

每进行一次活动,您的体力都会在活动前减少。 0 更大了,但活动结束后我的耐力下降了。 0 参与人数如下递增顺序请列举。

制約

  • 1 \leq N,Q \leq 200000
  • 1 \leq A_i \leq 10^9
  • 1 \leq x \leq N
  • 1 \leq y \leq 10^9
  • 在每个事件发生之前,参与者 x 有体力 这意味着第 0 大于
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。这里 这意味着第 event_i 是 您也可以写 i 个事件。

N Q
A_1 A_2 \cdots A_N
event_1
event_2
\vdots
event_Q

事件以下列格式之一给出。 在第

1 x y
2 x y

出力

Q 行。 在

i 行中,i 次事件之前,健康状况为 0 变大了,但是体力也变大了 0 以下参与者人数及其人数递增顺序请以空格分隔输出。


入力例 1

4 2
5 5 5 10
1 2 5
2 4 5

出力例 1

2 1 3
1 4

最初,每个参与者的体力为 (5,5,5,10) 。

1 第一场比赛结束后,每位参赛者的体力为 (0,5,0,5) 。

1 在第二个活动之前,你的体力将会降低。 0 变大了,但是体力也变大了 0 以下参与者为参与者。 1 和参与者 3 可以得到第 2 人。

2 第一场比赛结束后,每位参赛者的体力为 (0,5,0,0) 。

2 在第二个活动之前,你的体力将会降低。 0 变大了,但是体力也变大了 0 以下参与者为参与者。 4 可以得到第 1 人。


入力例 2

4 3
20 10 5 5
1 2 1
1 2 500
2 2 500

出力例 2

0
3 1 3 4
1 2