AT_abc287_g [ABC287G] Balance Update Query

题目描述

高桥君有 $N$ 种类的卡牌，每种卡牌各有 $10^{100}$ 张。最初，第 $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$

输出格式

设第 $3$ 类查询共有 $M$ 个。请输出 $M$ 行，第 $i$ 行输出第 $i$ 个 $3$ 类查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

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$ 类查询
• 所有输入均为整数

样例解释 1

对于第 $1$ 个 $3$ 类查询，可以选择第 $2$ 种卡牌 $1$ 张、第 $3$ 种卡牌 $3$ 张，得分总和为 $11$，这是最大值。
对于第 $2$ 个 $3$ 类查询，可以选择第 $1$ 种卡牌 $1$ 张、第 $3$ 种卡牌 $3$ 张，得分总和为 $19$，这是最大值。
对于第 $3$ 个 $3$ 类查询，无法选择 $4$ 张卡牌，因此输出 $-1$。
对于第 $4$ 个 $3$ 类查询，可以选择第 $2$ 种卡牌 $2$ 张，得分总和为 $4$，这是最大值。

由 ChatGPT 4.1 翻译