李超线段树
cpp
struct LichaoTree{
struct Node{
int l,r,id=0;
};
struct Line{
double k,b;
double f(double x){
return k*x+b;
}
};
const double eps=1e-9;
int cmp(double a,double b){
if(fabs(a-b)<eps)return 0;
if(a<b)return -1;
return 1;
}
vector<Node> t;
vector<Line> line;
void init(int n){
t.assign(n<<2,Node());
line.push_back({0,-INF});
}
void build(int p,int l,int r){
t[p]={l,r,0};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int id){
int mid=t[p].l+t[p].r>>1;
if(l<=t[p].l&&r>=t[p].r){
int tid=t[p].id;
if(cmp(line[id].f(mid),line[t[p].id].f(mid))>0)swap(t[p].id,id);
else if(cmp(line[id].f(mid),line[t[p].id].f(mid))==0&&t[p].id>id)swap(t[p].id,id);
if(t[p].l==t[p].r)return;
if(cmp(line[id].f(l),line[t[p].id].f(l))>=0)modify(p<<1,l,r,id);
if(cmp(line[id].f(r),line[t[p].id].f(r))>=0)modify(p<<1|1,l,r,id);
return;
}
if(l<=mid)modify(p<<1,l,r,id);
if(r>mid)modify(p<<1|1,l,r,id);
}
pair<double,int> query(int p,int x){
double res=line[t[p].id].f(x);
int id=t[p].id;
if(t[p].l==t[p].r)return {res,id};
int mid=t[p].l+t[p].r>>1;
if(x<=mid){
auto tmp=query(p<<1,x);
if(cmp(tmp.first,res)>0)res=tmp.first,id=tmp.second;
else if(cmp(tmp.first,res)==0&&id>tmp.second)id=tmp.second;
}
else{
auto tmp=query(p<<1|1,x);
if(cmp(tmp.first,res)>0)res=tmp.first,id=tmp.second;
else if(cmp(tmp.first,res)==0&&id>tmp.second)id=tmp.second;
}
return {res,id};
}
void add(int x0,int y0,int x1,int y1){
if(x0>x1)swap(x0,x1),swap(y0,y1);
double k,b;
if(x0!=x1){
k=1.0*(y1-y0)/(x1-x0);
b=y0-k*x0;
}
else{
k=0;
b=max(y0,y1);
}
line.push_back({k,b});
modify(1,x0,x1,line.size()-1);
}
};