Balance Update Query

题目描述

Takahashi 对每种共有 $10^{100}$ 张卡片，共有 $N$ 种。最初，第 $i$ 种卡片的分数和配额分别设为 $a_i$ 和 $b_i$。 给出 $Q$ 个按以下格式的查询，请按顺序处理它们。

$1 x y$: 将第 $x$ 种卡片的分数设为 $y$。 $2 x y$: 将第 $x$ 种卡片的配额设为 $y$。 $3 x$: 如果可以选择 $x$ 张卡且满足下面的条件，输出所选卡片分数之和的最大可能值；否则输出 $-1$。 每种所选卡片的数量不能超过其配额。

输入格式

输入从标准输入按以下格式给出，其中 $\mathrm{query}_i$ 表示第 $i$ 个查询： $N$ $a_1$ $b_1$ $\vdots$ $a_N$ $b_N$ $Q$ $\mathrm{query}_1$ $\vdots$ $\mathrm{query}_Q$

输出格式

输出 $M$ 行，其中 $M$ 为第 3 类查询的数量。
第 $i$ 行应包含对第 $i$ 个此类查询的回答。

3
1 1
2 2
3 3
7
3 4
1 1 10
3 4
2 1 0
2 3 0
3 4
3 2

11
19
-1
4

提示

$1 \leq N,Q \leq 2 \times 10^5$ $0 \leq a_i \leq 10^9$ $0 \leq b_i \leq 10^4$ 对于第 1 类查询，$1 \leq x \leq N$ 且 $0 \leq y \leq 10^9$。 对于第 2 类查询，$1 \leq x \leq N$ 且 $0 \leq y \leq 10^4$。 对于第 3 类查询，$1 \leq x \leq 10^9$。 至少有一个第 3 类查询。 输入中的所有数值均为整数。对于第一个第 3 类查询，你可以选择一张第 2 种卡和三张第 3 种卡，总分为 $11$，这是最大值。
对于第二个此类查询，你可以选择一张第 1 种卡和三张第 3 种卡，总分为 $19$，这是最大值。
对于第三个此类查询，你无法选择四张卡，因此应输出 $-1$。
对于第四个此类查询，你可以选择两张第 2 种卡，总分为 $4$，这是最大值。

标签: AtCoder|abc287G

来源

AtCoder|abc287G