传送门
题意：
支持插入一个向量，删去某一个现有的向量，查询现有的所有向量与给出的一个向量的点积的最大值。
思路：
考虑线段树分治。
先对于每个向量处理出其有效时间放到线段树上面，然后考虑查询：对于两个已有的向量(u1,v1)(u_1,v_1)(u1,v1)和(u2,v2)(u_2,v_2)(u2,v2)，假设给出的向量为(x0,y0)(x_0,y_0)(x0,y0)u1>u2&&(u1,v1)⋅(x0,y0)>(u2,v2)⋅(x0,y0)u_1>u_2\&\&(u_1,v_1)\cdot(x_0,y_0)>(u_2,v_2)\cdot(x_0,y_0)u1>u2&&(u1,v1)⋅(x0,y0)>(u2,v2)⋅(x0,y0)
那么展开得知：(u1−u2)x0>−(v1−v2)y0⇒−x0y0>v1−v2u1−u2(u_1-u_2)x_0>-(v_1-v_2)y_0\Rightarrow-\frac{x_0}{y_0}>\frac{v_1-v_2}{u_1-u_2}(u1−u2)x0>−(v1−v2)y0⇒−y0x0>u1−u2v1−v2
说明在凸包上，于是对于每个线段树节点维护一个凸包，查询的时候在上面二分即可。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=200005;
int n,tot1=0,tot2=0,q[N],top;
struct Node{int l,r;ll x,y;}a[N];
ll ans[N];
struct pot{
ll x,y;
pot(ll _x=0,ll _y=0):x(_x),y(_y){}
friend inline pot operator+(const pot&a,const pot&b){return pot(a.x+b.x,a.y+b.y);}
friend inline pot operator-(const pot&a,const pot&b){return pot(a.x-b.x,a.y-b.y);}
friend inline ll operator^(const pot&a,const pot&b){return a.x*b.y-a.y*b.x;}
friend inline ll operator*(const pot&a,const pot&b){return a.x*b.x+a.y*b.y;}
friend inline bool operator<(const pot&a,const pot&b){return a.x==b.x?a.y<b.y:a.x<b.x;}
}b[N];
typedef pair<int,pot> pii;
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
vector<pot>upd[N<<2];
inline void update(int p,int l,int r,int ql,int qr,pot v){
if(ql>r||qr<l)return;
if(ql<=l&&r<=qr)return upd[p].push_back(v);
if(qr<=mid)update(lc,l,mid,ql,qr,v);
else if(ql>mid)update(rc,mid+1,r,ql,qr,v);
else update(lc,l,mid,ql,qr,v),update(rc,mid+1,r,ql,qr,v);
}
inline ll max(const ll&a,const ll&b){return a>b?a:b;}
inline ll max(const ll&a,const ll&b,const ll&c){return a>b?(a>c?a:c):(b>c?b:c);}
inline double slope(pot a,pot b){return a.x==b.x?1e9:(double)(a.y-b.y)/(double)(a.x-b.x);}
inline ll query(int p,pot tmp){
ll ret=0;
if(top<=3){
for(ri i=1;i<=top;++i)ret=max(ret,tmp*upd[p][q[i]]);
return ret;
}
double slop=-(double)tmp.x/(double)tmp.y;
if(slop>slope(upd[p][q[2]],upd[p][q[1]]))return tmp*upd[p][q[1]];
if(slop<slope(upd[p][q[top]],upd[p][q[top-1]]))return tmp*upd[p][q[top]];
ret=max(tmp*upd[p][q[1]],tmp*upd[p][q[top]]);
int l=2,r=top,res=1;
while(l<=r){
int Mid=l+r>>1;
if(slop<slope(upd[p][q[Mid]],upd[p][q[Mid-1]]))l=Mid+1,res=Mid;
else r=Mid-1;
}
return tmp*upd[p][q[res]];
}
inline void calc(int p,int l,int r){
if(!upd[p].size())return;
sort(upd[p].begin(),upd[p].end());
q[top=1]=0;
for(ri i=1,up=upd[p].size()-1;i<=up;++i){
while(top>1&&((upd[p][i]-upd[p][q[top-1]])^(upd[p][q[top]]-upd[p][q[top-1]]))<=0)--top;
q[++top]=i;
}
for(ri i=l;i<=r;++i)ans[i]=max(ans[i],query(p,b[i]));
}
inline void solve(int p,int l,int r){
calc(p,l,r);
if(l==r)return;
solve(lc,l,mid),solve(rc,mid+1,r);
}
#undef lc
#undef rc
#undef mid
int main(){
n=read();
for(ri op,x,y,i=1;i<=n;++i){
op=read();
if(op==1)x=read(),y=read(),a[++tot1]=(Node){tot2+1,-1,x,y};
if(op==2)a[read()].r=tot2;
if(op==3)b[++tot2].x=read(),b[tot2].y=read();
}
for(ri i=1;i<=tot1;++i)update(1,1,tot2,a[i].l,~a[i].r?a[i].r:tot2,pot(a[i].x,a[i].y));
solve(1,1,tot2);
for(ri i=1;i<=tot2;++i)cout<<ans[i]<<'\n';
return 0;
}