change 在x坐标区间[l,r]上新增编号为id的线段（x坐标范围为[L,R] ），更新最大y值

query 查询x坐标区间[l,r]上的最大

#define N 50005
#define ls u<<1
#define rs u<<1|1
int n,cnt;
struct line{
  double k,b; //斜率,截距
}p[N*2];
int tr[N*4]; //线段编号

double Y(int id,int x){ //求Y值
  return p[id].k*x+p[id].b;
}
void change(int u,int l,int r,int L,int R,int id){ //修改
  int mid=(l+r)>>1;
  if(L<=l&&r<=R){
    if(Y(id,mid)>Y(tr[u],mid)) swap(id,tr[u]);
    if(Y(id,l)>Y(tr[u],l)) change(ls,l,mid,L,R,id);
    if(Y(id,r)>Y(tr[u],r)) change(rs,mid+1,r,L,R,id);
    return;
  }
  if(L<=mid) change(ls,l,mid,L,R,id);
  if(mid<R) change(rs,mid+1,r,L,R,id);
}
double query(int u,int l,int r,int x){ //查询
  if(l==r) return Y(tr[u],x);
  int mid=(l+r)>>1;
  double t=Y(tr[u],x);
  if(x<=mid) return max(t,query(ls,l,mid,x));
  else return max(t,query(rs,mid+1,r,x));
}

如果插入的是直线，认为线段范围包含了整个区间，条件L<=l&&r<=R 必定成立。

维护所有直线的上凸壳

using ll = long long;
#define N 100005
#define ls u<<1
#define rs u<<1|1
struct line{
    ll k,b; //斜率,截距
} p[N*2];
int tr[N*4]; //线段编号
int cnt = 0;
ll Y(int id,int x){ //求Y值
    return p[id].k*x+p[id].b;
}
void change(int u,int l,int r,int id){ //修改
    int mid=(l+r)>>1;
    if(Y(id,mid)>Y(tr[u],mid)) swap(id,tr[u]);
    if(Y(id,l)>Y(tr[u],l)) change(ls,l,mid,id);
    if(Y(id,r)>Y(tr[u],r)) change(rs,mid+1,r,id);
}
ll query(int u,int l,int r,int x){ //查询
    if(l==r) return Y(tr[u],x);
    int mid=(l+r)>>1;
    ll t=Y(tr[u],x);
    if(x<=mid) return max(t,query(ls,l,mid,x));
    else return max(t,query(rs,mid+1,r,x));
}
void addline(ll k, ll b) {
    p[++cnt] = {k, b};
    change(1, 0, N, cnt);
}