← 返回题目列表

Codeforces · 1515/I

I. 凤凰与钻石

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

菲尼克斯想知道从珠宝店抢劫钻石是什么感觉!

钻石有 $$$n$$$ 种类型。第 $$$i$$$ 类型的权重为 $$$w_i$$$ ,值为 $$$v_i$$$。商店最初拥有第 $$$i$$$ 类型的 $$$a_i$$$ 钻石。

每天,在 $$$q$$$ 天里,都会发生以下情况之一:

1. 一批新的 $$$k_i$$$ 类型 $$$d_i$$$ 钻石抵达。
2. 商店出售 $$$k_i$$$ 类型 $$$d_i$$$ 钻石。
3. 菲尼克斯想知道如果他用一个可以装总重量不超过$$$c_i$$$的钻石的袋子抢劫商店会发生什么。如果他贪婪地拿走价值最大的合适的钻石,会拿走多少价值?如果有多颗价值最大的钻石,他会选择重量最小的一颗。如果价值最大的钻石中,有多颗最小重量相同的钻石,他就拿走其中的任何一个。

当然,由于菲尼克斯是一个守法公民,所以这只是一个思想实验,他从未真正从商店里抢劫过任何钻石。这意味着 $$$3$$$ 类型的查询不会影响商店中的钻石。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$)——分别是钻石类型的数量和天数。

接下来的 $$$n$$$ 行描述了每种类型的钻石。第 $$$i$$$ 行将包含三个整数 $$$a_i$$$、$$$w_i$$$ 和 $$$v_i$$$ ($$$0 \le a_i \le 10^5$$$; $$$1 \le w_i, v_i \le 10^5$$$) - 第 $$$i$$$ 类型的钻石的初始数量、钻石的重量分别是第 $$$i$$$ 类型的钻石,以及第 $$$i$$$ 类型的钻石的价值。

接下来的 $$$q$$$ 行包含查询。对于每个查询,每行的第一个整数是 $$$t$$$ ($$$1 \le t \le 3$$$) — 查询的类型。

如果$$$t=1$$$,则后面是两个整数$$$k_i$$$、$$$d_i$$$ ($$$1 \le k_i \le 10^5$$$; $$$1 \le d_i \le n$$$)。这意味着新一批 $$$k_i$$$ 钻石已抵达,每颗钻石类型为 $$$d_i$$$。

如果$$$t=2$$$,则后面是两个整数$$$k_i$$$、$$$d_i$$$ ($$$1 \le k_i \le 10^5$$$; $$$1 \le d_i \le n$$$)。这意味着商店已售出 $$$k_i$$$ 颗钻石,每颗钻石类型为 $$$d_i$$$。保证商店在出售钻石之前就拥有这些钻石。

如果$$$t=3$$$,则后面会跟随一个整数$$$c_i$$$ ($$$1 \le c_i \le 10^{18}$$$)——Phoenix 包的重量容量。

保证至少有一个$$$t=3$$$ 的查询。

输出

打印第三种类型的每个查询的答案 ($$$t=3$$$)。

示例

输入 #1

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

输出 #1

8
16
13

注意

对于 $$$t=3$$$ 的第一个查询,Phoenix 可以容纳 $$$2$$$ 类型 $$$1$$$ 的钻石,总重量为 $$$6$$$,价值为 $$$8$$$。

对于 $$$t=3$$$ 的第二个查询,Phoenix 将首先放入 $$$3$$$ 类型的 $$$3$$$ 钻石,然后放入一颗 $$$1$$$ 类型的钻石,总重量为 $$$9$$$,价值为 $$$16$$$。请注意,$$$3$$$ 类型的钻石优先于 $$$1$$$ 类型的钻石,因为 $$$3$$$ 类型的钻石具有相同的价值,但重量更轻。

对于 $$$t=3$$$ 的最终查询,Phoenix 可以拟合总价值为 $$$13$$$ 的每颗钻石。