shallot+向量集 混合版？
首先我们考虑每个向量的存在时间为[L,R]
那么我们知道任意一个区间在线段树上最多被分解成logn个区间
那么我们可以像shallot一样进行区间覆盖
注意到本题的查询是在凸壳上完成的，而凸壳不像shallot的线性基一样有固定的时间复杂度
但是本题的查询是可分离的，那么我们不需要将向量下传，只需要在线段树的每一层做凸壳即可
查询时每走一层对该层三分取最优解，建造凸壳和三分方法同向量集
QAQ 上午因为排序不小心写反了符号调了好久 QAQ
时间复杂度O(nlog^2n)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<vector>
using namespace std; typedef long long LL;
const int maxn=200010;
const LL oo=1LL<<62;
int n,m,f,x,cnt;
int top=0;
int L[maxn],R[maxn];
struct Point{
int x,y;
Point(int x=0,int y=0):x(x),y(y){}
void print(){printf("%d %d\n",x,y);}
}p[maxn],st[4000010],now;
typedef Point Vector;
bool cmp(const Point &A,const Point &B){
if(A.x==B.x)return A.y<B.y;
return A.x<B.x;
}
Vector operator -(const Point &A,const Point &B){return Vector(A.x-B.x,A.y-B.y);}
LL Cross(const Point &A,const Point &B){return 1LL*A.x*B.y-1LL*A.y*B.x;}
LL Dot(const Point &A,const Point &B){return 1LL*A.x*B.x+1LL*A.y*B.y;}
struct ASK{
int x,y,t;
}Q[maxn];
struct Seg_Tree{
vector<Point>V;
int A,B;
void Get_Hull(){
A=top+1;
int sz=V.size();
sort(V.begin(),V.end(),cmp);
for(int i=0;i<sz;++i){
while(top>A&&Cross(V[i]-st[top],st[top]-st[top-1])<=0)top--;
st[++top]=V[i];
}B=top;
}
LL Max(){
if(V.empty())return 0;
if(!A)Get_Hull();
int L=A,R=B;
LL ans=0;
while(R-L>=3){
int m1=(L+L+R)/3,m2=(L+R+R)/3;
if(Dot(st[m1],now)<=Dot(st[m2],now))L=m1;
else R=m2;
}
for(int i=L;i<=R;++i)ans=max(ans,Dot(st[i],now));
return ans;
}
}t[maxn<<2];
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void modify(int o,int L,int R,int x,int y,int id){
if(L>=x&&R<=y){
t[o].V.push_back(p[id]);
return;
}
int mid=(L+R)>>1;
if(y<=mid)modify(o<<1,L,mid,x,y,id);
else if(x>mid)modify(o<<1|1,mid+1,R,x,y,id);
else modify(o<<1,L,mid,x,y,id),modify(o<<1|1,mid+1,R,x,y,id);
}
LL ask(int o,int L,int R,int p){
if(L==R)return t[o].Max();
int mid=(L+R)>>1;
if(p<=mid)return max(t[o].Max(),ask(o<<1,L,mid,p));
else return max(t[o].Max(),ask(o<<1|1,mid+1,R,p));
}
int main(){
read(n);
for(int i=1;i<=n;++i){
read(f);
if(f==1){
++cnt;
read(p[cnt].x);read(p[cnt].y);
L[cnt]=i;
}else if(f==2){
read(x);R[x]=i;
}else{
++m;
read(Q[m].x);read(Q[m].y);
Q[m].t=i;
}
}
for(int i=1;i<=cnt;++i){
if(!R[i])R[i]=n;
modify(1,1,n,L[i],R[i],i);
}
for(int i=1;i<=m;++i){
now=Point(Q[i].x,Q[i].y);
printf("%lld\n",ask(1,1,n,Q[i].t));
}
return 0;
}