题目大意：要求对一个点集实现二维点对的插入，删除，以及询问(q)：求(max(xcdot q+y))
题解：对每个点集内的点(P(x_0,y_0))，作过点(P)且斜率为(-q)的直线(l)，则有(l:y-y_0=-q(x-x_0))，可以发现当(x=0)时，有(y=qcdot 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<<2]; void Build(LL l,LL r,LL x) { t[x].l=l,t[x].r=r; if(l==r)return; LL mid=l+r>>1; Build(l,mid,x*2); Build(mid+1,r,x*2+1); } void change(LL L,LL R,Point p,LL x) { LL l=t[x].l,r=t[x].r; LL mid=l+r>>1; if(L<=l && r<=R){t[x].s.insert(p);return;} if(L<=mid)change(L,R,p,x*2); if(mid<R)change(L,R,p,x*2+1); } void ask(LL x) { LL l=1,r=cnt; while(l+2<r) { LL mid1=(2*l+r)/3; LL mid2=(l+2*r)/3; 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*2); get(x*2+1); } cnt=0; for(auto p:t[x].s) { while(cnt>1 && (st[cnt]-st[cnt-1])*(p-st[cnt])>=0)cnt--; st[++cnt]=p; } for(LL i=t[x].l;i<=t[x].r;i++) if(o[i]==3 && c[i])ask(i); } }T; int main() { scanf("%I64d",&n); T.Build(1,n,1); for(LL i=1;i<=n;i++) { scanf("%I64d",&o[i]); if(o[i]==1) { scanf("%I64d%I64d",&x[i],&y[i]); r[i]=n,cnt++; } if(o[i]==2) { scanf("%I64d",&q[i]); r[q[i]]=i,cnt--; } if(o[i]==3) { scanf("%I64d",&q[i]),f[i]=-(5e18); } c[i]=cnt; } for(LL i=1;i<=n;i++) if(o[i]==1)T.change(i,r[i],{x[i],y[i]},1); T.get(1); for(LL i=1;i<=n;i++) if(o[i]==3) if(c[i])printf("%I64d ",f[i]); else printf("EMPTY SET "); }