logo AlgoBeat OnlineJudge
登录 注册

#214368. [LBA-OI R2 A] 一次买够

内存限制:512 MiB 时间限制:799 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小清新签到题~


小 Y 非常有钱,所以她可以买下所有她想要的东西。

今天,她来到商店购物。商店有 件商品,第 件商品的价格为 ,性价比为 。一开始,小 Y 会买下性价比最大的所有商品(如果有多个就全部买下)。接下来,有 个事件依次发生,第 个事件可能为以下两种类型之一:

  1. 新增一件价格为 ,性价比为 的商品,其编号为
  2. 将编号为 的商品的性价比更改为

请注意,一旦小 Y 买下了某件商品,之后即使这件商品的性价比降低,小 Y 也不会出售这件商品。

每次事件后,计算小 Y 已买下商品中的最低性价比 ,小 Y 会在此时买下所有性价比 的未被购买的商品。

作为小 Y 的生活助理,你需要统计每次事件后小 Y 的总花销。

输入格式

第一行,两个整数 ,分别表示商品数与事件数。

接下来 行,第 行包含两个整数

接下来 行,第 行包含三个整数 ,其中 表明事件 是新增商品事件, 表明事件 是修改性价比事件。

输出格式

输出共 行。第 行包含一个整数,表示事件 后小 Y 的总花销。

样例

样例输入 1

6 4
1 1
1 2
1 3
1 4
1 5
1 5
2 5 4
1 10 3
2 8 4
2 5 2

样例输出 1

3
3
13
15

样例输入 2

5 5
11 4
13 6
14 3
20 8
0 5
2 4 5
2 5 0
2 4 10
1 12 2
2 1 0

样例输出 2

33
58
58
70
70

数据范围与提示

样例解释 1

初始,编号为 的商品性价比最高,因此所有小 Y 购买的商品为

事件 中,商品 的性价比被修改为 。此时有 ,因此小 Y 购买商品 ,而其余商品仍未被购买。此时所有小 Y 购买的商品为

事件 中,新增了一件商品,其编号为 ,但其性价比只有 ,因此小 Y 没有购买它。

事件 中,商品 的性价比被修改为 ,此时小 Y 购买商品 ,现在所有她购买的商品为

事件 中,商品 的性价比被修改为 ,最终所有小 Y 购买的商品为

数据范围

子任务编号 特殊性质 分值

对于所有数据:保证 。若 ,则 ,否则保证编号为 的商品已经存在。