P14962 [LBA-OI R2 A] 一次买够

小清新签到题~

小 Y 非常有钱，所以她可以买下所有她想要的东西。 今天，她来到商店购物。商店有 $n$ 件商品，第 $i$ 件商品的价格为 $v_i$，性价比为 $w_i$。一开始，小 Y 会买下性价比最大的所有商品（如果有多个就全部买下）。接下来，有 $m$ 个事件依次发生，第 $i\;(1 \leq i \leq m)$ 个事件可能为以下两种类型之一： 1. 新增一件价格为 $x_i$，性价比为 $y_i$ 的商品，其编号为 $n+i$； 2. 将编号为 $x_i$ 的商品的性价比更改为 $y_i$。 **请注意，一旦小 Y 买下了某件商品，之后即使这件商品的性价比降低，小 Y 也不会出售这件商品。** 每次事件后，计算小 Y 已买下商品中的最低性价比 $L$，小 Y 会在此时买下所有性价比 $\ge L$ 的未被购买的商品。 作为小 Y 的生活助理，你需要统计每次事件后小 Y 的总花销。

第一行，两个整数 $n, m$，分别表示商品数与事件数。 接下来 $n$ 行，第 $i$ 行包含两个整数 $v_i, w_i$。 接下来 $m$ 行，第 $i$ 行包含三个整数 $o_i, x_i, y_i$，其中 $o_i = 1$ 表明事件 $i$ 是新增商品事件，$o_i = 2$ 表明事件 $i$ 是修改性价比事件。

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

#### 样例解释 1 初始，编号为 $5, 6$ 的商品性价比最高，因此所有小 Y 购买的商品为 $\{5, 6\}$。 事件 $1$ 中，商品 $5$ 的性价比被修改为 $4$。此时有 $w_4 \geq w_5$，因此小 Y 购买商品 $4$，而其余商品仍未被购买。此时所有小 Y 购买的商品为 $\{4, 5, 6\}$。 事件 $2$ 中，新增了一件商品，其编号为 $6+2=8$，但其性价比只有 $3$，因此小 Y 没有购买它。 事件 $3$ 中，商品 $8$ 的性价比被修改为 $4$，此时小 Y 购买商品 $8$，现在所有她购买的商品为 $\{4, 5, 6, 8\}$。 事件 $4$ 中，商品 $5$ 的性价比被修改为 $2$，最终所有小 Y 购买的商品为 $\{2, 3, 4, 5, 6, 8\}$。 #### 数据范围 | 子任务编号 | 特殊性质 | 分值 | | :-------------: | :-----------: | :-----: | | $1$ | $n, m \leq 3000$ | $60$ | | $2$ | $w_i, y_i \leq 10$ | $15$ | | $3$ | — | $25$ | 对于所有数据：保证 $1 \leq n \leq 2\times 10^5$，$1 \leq m \leq 2\times 10^5$，$0 \leq v_i, w_i, y_i \leq 10^9$，$o_i \in \{1, 2\}$。若 $o_i = 1$，则 $0 \leq x_i \leq 10^9$，否则保证编号为 $x_i$ 的商品已经存在。