CF678F Lena and Queries

Lena 是一名程序员。她在工作中接到一个任务，需要处理如下操作。 现在有一个整数对的空集合，以及 $n$ 个需要依次处理的操作。每个操作有三种类型之一： 1. 向集合中加入一个数对 $(a,b)$。 2. 移除在第 $i$ 个操作中加入的数对。所有操作按 $1$ 到 $n$ 编号。 3. 给定一个整数 $q$，对于当前集合中的所有数对 $(x,y)$，求最大的 $x\cdot q+y$。 请你帮助 Lena 依次处理这些操作。

第一行输入一个整数 $n$（$1\leq n\leq 3\cdot10^{5}$），表示操作的总数。 接下来的 $n$ 行，每行描述一个操作，格式如下： - 第一类操作：以 $1$ 开头，后接两个整数 $a$ 和 $b$（$-10^{9}\leq a,b\leq 10^{9}$），表示向集合中添加一个数对 $(a,b)$。 - 第二类操作：以 $2$ 开头，后接一个整数 $i$（$1\leq i\leq n$），表示移除第 $i$ 个操作中添加的数对。保证 $i$ 小于当前操作编号，第 $i$ 个操作是第一类操作，并且该对没有被移除过。 - 第三类操作：以 $3$ 开头，后接一个整数 $q$（$-10^{9}\leq q\leq 10^{9}$），表示询问当前集合中所有数对 $(x,y)$ 的 $x\cdot q+y$ 的最大值。

对于每个第三类操作，输出一行答案。若当前集合为空，输出 `EMPTY SET`。

由 ChatGPT 5 翻译