一、题目
二、解法
线段树分治可以解决在线插入难，在线删除难，回退难的问题。
就好比我们只会凸包的离线插入，那么在线段树上的每一个节点上维护一个凸包，然后去更新它管辖区间的所有询问即可，每个询问只会被更新 (log) 次所以复杂度是对的。
忘了说这道题为什么要用凸包了，对于询问 ((x,y)) 考虑两个向量 ((x_1,y_1),(x_2,y_2))，设 (x_1<x_2)，那么第二个向量比第一个向量更优的条件是：
[xx_1+yy_1<xx_2+yy_2
]
[frac{-y_2+y_1}{x_2-x_1}<frac{x}{y}
]
这相当于维护一个 ((x_i,-y_i)) 的下凸包，然后找第一个斜率大于等于 (frac{x}{y}) 的线段即可。
实现细节：以总操作个数来建线段树，避免以询问个数来建线段树的细节，如果你调不出来就暴力访问凸包上的每个点，然后发现可以直接过掉。
#include <cstdio>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 2000005;
#define db double
#define ll long long
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,tp,vx[M],vy[M],vl[M],vr[M],qx[M],qy[M],id[M];
vector<int> p[4*M];ll nx,ny,ans[M];int v[M];db kk[M];
void ins(int i,int l,int r,int L,int R,int x)
{
if(L>r || l>R) return ;
if(L<=l && r<=R)
{
p[i].push_back(x);
return ;
}
int mid=(l+r)>>1;
ins(i<<1,l,mid,L,R,x);
ins(i<<1|1,mid+1,r,L,R,x);
}
int cmp(int x,int y)
{
return vx[x]==vx[y]?vy[x]<vy[y]:vx[x]<vx[y];
}
db slope(int x,int y)
{
return 1.0*(vy[x]-vy[y])/(vx[y]-vx[x]);
}
void work(int x)
{
tp=0;
sort(p[x].begin(),p[x].end(),cmp);
for(int i=0,sz=p[x].size();i<sz;i++)
{
int t=p[x][i];
while(tp>1 && slope(v[tp],t)
<=slope(v[tp-1],v[tp])) tp--;
v[++tp]=t;
}
v[tp+1]=0;
for(int i=1;i<tp;i++)
kk[i]=slope(v[i],v[i+1]);
}
ll dot(int x)
{
return vx[x]*nx+vy[x]*ny;
}
void zxy(int x)
{
nx=qx[x];ny=qy[x];
int t=lower_bound(kk+1,kk+tp,1.0*nx/ny)-kk;
//for(int i=1;i<=tp;i++)
// ans[x]=max(ans[x],dot(v[i]));
if(t>tp) return ;
ans[x]=max(ans[x],dot(v[t]));
ans[x]=max(ans[x],dot(v[t-1]));
ans[x]=max(ans[x],dot(v[t+1]));
//return max(dot(v[t]),dot(v[t+1]));
}
void build(int i,int l,int r)
{
work(i);
for(int i=l;i<=r;i++)
if(id[i]) zxy(id[i]);
if(l==r) return ;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
}
signed main()
{
//freopen("1.in","r",stdin);
//freopen("zxy.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
int t=read();
if(t==1)
{
m++;vl[m]=i;
vx[m]=read();vy[m]=read();
}
if(t==2)
vr[read()]=i;
if(t==3)
qx[++k]=read(),qy[k]=read(),id[i]=k;
}
for(int i=1;i<=m;i++)
{
if(vr[i]==0) vr[i]=n;
ins(1,1,n,vl[i],vr[i],i);
}
build(1,1,n);
for(int i=1;i<=k;i++)
printf("%lld
",ans[i]);
}