P14109 [ZJCPC 2017] Card Game

Alice 和 Bob 又开始玩游戏了。这次的游戏和石子无关，而是一个纸牌游戏。 桌面上有 $n$ 张牌，每张牌上写有两个整数（一个表示红色，一个表示蓝色）。每一轮开始时，会给出两个整数 $L$ 和 $R$。Alice 需要选择一个整数 $x$，满足 $L \le x \le R$，并将她的选择告诉 Bob。在得知 $x$ 后，Bob 会从桌面上选择一张牌。本轮得分等于 $rx + b$，其中 $r$ 表示所选牌上的红色整数，$b$ 表示该牌上的蓝色整数。 Alice 和 Bob 都可以在做出决策前自由查看桌面上的所有牌及其整数。 为了让游戏更加有趣，在某一轮前可以进行如下操作： - 向桌面上加入一张写有红色和蓝色整数的新牌。 - 移除桌面上的一张牌。 Alice 希望每一轮都最大化得分，而 Bob 则希望最小化得分。如果两人都采取最优策略，你能求出每一轮的最终得分么？

输入包含多组测试数据。第一行为一个整数 $T$，表示测试数据组数。对于每组测试数据： 第一行包含两个整数 $n$（$1 \le n \le 5 \times 10^4$）和 $q$（$1 \le q \le 5 \times 10^4$），表示初始在桌面上的牌数和操作数。 接下来的 $n$ 行，每行包含两个整数 $r_i$ 和 $b_i$（$-10^9 \le r_i, b_i \le 10^9$），表示初始时有一张牌，其红色数为 $r_i$、蓝色数为 $b_i$。 接下来的 $q$ 行，每行包含三个整数 $op$（$0 \le op \le 2$）、$a$、$b$（$-10^9 \le a, b \le 10^9$）。 - 若 $op = 0$，表示你需要计算该回合的最终得分，给定 $L = a$ 和 $R = b$。保证此时 $a \le b$。 - 若 $op = 1$，表示将一张红色数为 $a$，蓝色数为 $b$ 的新牌放到桌面上。 - 若 $op = 2$，表示要移除一张红色数为 $a$，蓝色数为 $b$ 的牌。保证这张牌存在于桌面上。如果有多张满足的牌，只移除一张即可。 保证所有测试数据中 $n$ 和 $q$ 的总和不超过 $2 \times 10^5$。 请注意，本题输入输出数据量较大，建议使用更快的输入输出方式。例如，C++ 中可以使用 scanf/printf 替代 cin/cout。

对于每个 $op = 0$ 的操作，输出一行，表示该回合的最终得分。

由 ChatGPT 5 翻译