好题。
大致题面：
动态加入删除直线 \(kx+b\)，查询所有直线过某条竖线 \(x=p\) 的最高点。
这个不带删除显然是李超树模板题，但是李超树不可以进行删除。一般来说，我们可以考虑线段树分治来解决这一类难以删除的问题。
一个不成熟的想法是把李超树交换节点的信息存储到了栈里，然后交换，这个是可以做的。
但是我们可以保留线段树分治的想法。因为动态开点李超树的空间是 \(O(n)\) 的，所以我们可以考虑线段树套动态开点李超树，然后把其每一条直线存在的时间段若干 \([l_i, r_i]\) 插入这一条直线。
查询就直接查询从该点到根的路径上套的所有李超树的过该竖线的最大值就行了。
然后我们就可以时间 \(O(n\log n \log v)\)，空间 \(O(n\log n)\) 来解决这一个问题，代码实现是简易的。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, MOD = 998244353;
int n, op[N], k[N], b[N], lp[N], rp[N], rt[N << 2], tot, pos[N];
int lc[N << 5], rc[N << 5], id[N << 5];
inline long long val (int x, int i) { return 1ll * k[i] * x + b[i]; }
inline void insert (int & u, int l, int r, int p) {
if (! u) u = ++ tot;
if (! id[u]) return id[u] = p, void();
int mid = (l + r) >> 1;
if (val(mid, p) > val(mid, id[u])) swap(id[u], p);
if (val(l, p) > val(l, id[u])) insert(lc[u], l, mid, p);
if (val(r, p) > val(r, id[u])) insert(rc[u], mid + 1, r, p);
}
inline long long query (int u, int l, int r, int p) {
if (! u) return LLONG_MIN;
long long res = val(p, id[u]);
if (l == r) return res;
int mid = (l + r) >> 1;;
if (p <= mid) return max(res, query(lc[u], l, mid, p));
else return max(res, query(rc[u], mid + 1, r, p));
}
#define ls u << 1
#define rs u << 1 | 1
inline void build (int u, int l, int r) {
if (l == r) return pos[l] = u, void();
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
}
inline void assign (int u, int l, int r, int ql, int qr, int x) {
if (ql <= l && r <= qr) insert(rt[u], -1e9, 1e9, x);
else {
int mid = (l + r) >> 1;
if (ql <= mid) assign(ls, l, mid, ql, qr, x);
if (qr > mid) assign(rs, mid + 1, r, ql, qr, x);
}
}
int main () {
ios :: sync_with_stdio(0);
cin >> n, build(1, 1, n);
for (int i = 1, idx; i <= n; i ++) {
cin >> op[i];
if (op[i] == 1) cin >> k[i] >> b[i], lp[i] = i, rp[i] = n;
else if (op[i] == 2) cin >> idx, rp[idx] = i;
else cin >> k[i];
}
for (int i = 1; i <= n; i ++) if (op[i] == 1) assign(1, 1, n, lp[i], rp[i], i);
for (int i = 1; i <= n; i ++)
if (op[i] == 3) {
long long ans = LLONG_MIN;
for (int u = pos[i]; u; u >>= 1) ans = max(ans, query(rt[u], -1e9, 1e9, k[i]));
if (ans == LLONG_MIN) puts("EMPTY SET");
else printf("%lld\n", ans);
}
return 0;
}