题目大意：要求对一个点集实现二维点对的插入，删除，以及询问\(q\)：求\(max(x\cdot q+y)\)
题解：对每个点集内的点\(P(x_0,y_0)\)，作过点\(P\)且斜率为\(-q\)的直线\(l\)，则有\(l:y-y_0=-q(x-x_0)\)，可以发现当\(x=0\)时，有\(y=q\cdot x_0+y_0\)。因此只要找到一个点，使得过此点作斜率为\(-q\)的直线在\(y\)轴上的截距最大即可。可以发现满足条件的点一定在一个上凸壳上，所以可以用三分来解决问题
但由于需要处理点的插入和删除操作，直接在线求解比较麻烦，所以考虑离线处理询问
因此我们只要记录每一个点的存在时间段，对时间建线段树，对线段树上的每一个节点暴力求出答案即可。由于每一个插入的点只会影响到\(log\ n\)个节点，所以总复杂度是\(O(nlog^2n)\)的
#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define LL long long
struct Point
{
LL x,y;
Point operator -(const Point &t)const{return{x-t.x,y-t.y};}
LL operator *(const Point &t)const{return x*t.y-y*t.x;}
bool operator <(const Point &t)const{return x==t.x?y<t.y:x<t.x;}
}st[N];
LL n,cnt,o[N],q[N],f[N],c[N],r[N],x[N],y[N];
struct Segment_Tree
{
struct rua
{
LL l,r;
set<Point>s;
}t[N<<];
void Build(LL l,LL r,LL x)
{
t[x].l=l,t[x].r=r;
if(l==r)return;
LL mid=l+r>>;
Build(l,mid,x*);
Build(mid+,r,x*+);
}
void change(LL L,LL R,Point p,LL x)
{
LL l=t[x].l,r=t[x].r;
LL mid=l+r>>;
if(L<=l && r<=R){t[x].s.insert(p);return;}
if(L<=mid)change(L,R,p,x*);
if(mid<R)change(L,R,p,x*+);
}
void ask(LL x)
{
LL l=,r=cnt;
while(l+<r)
{
LL mid1=(*l+r)/;
LL mid2=(l+*r)/;
if(q[x]*st[mid1].x+st[mid1].y<q[x]*st[mid2].x+st[mid2].y)l=mid1;
else r=mid2;
}
for(LL i=l;i<=r;i++)f[x]=max(f[x],q[x]*st[i].x+st[i].y);
}
void get(LL x)
{
if(t[x].l<t[x].r)
{
get(x*);
get(x*+);
}
cnt=;
for(auto p:t[x].s)
{
while(cnt> && (st[cnt]-st[cnt-])*(p-st[cnt])>=)cnt--;
st[++cnt]=p;
}
for(LL i=t[x].l;i<=t[x].r;i++)
if(o[i]== && c[i])ask(i);
}
}T;
int main()
{
scanf("%I64d",&n);
T.Build(,n,);
for(LL i=;i<=n;i++)
{
scanf("%I64d",&o[i]);
if(o[i]==)
{
scanf("%I64d%I64d",&x[i],&y[i]);
r[i]=n,cnt++;
}
if(o[i]==)
{
scanf("%I64d",&q[i]);
r[q[i]]=i,cnt--;
}
if(o[i]==)
{
scanf("%I64d",&q[i]),f[i]=-(5e18);
}
c[i]=cnt;
}
for(LL i=;i<=n;i++)
if(o[i]==)T.change(i,r[i],{x[i],y[i]},);
T.get();
for(LL i=;i<=n;i++)
if(o[i]==)
if(c[i])printf("%I64d\n",f[i]);
else printf("EMPTY SET\n");
}