\(LiChao-Tree\)

简称LCT
维护一些与斜率相关的东西，一次函数等等

\(calc(a,pos):\)用来计算\(y = k_a \times x + b_a\),其中横坐标\(x = pos\)

inline db calc (int x,int pos){return k[x] * (pos - 1) + b[x];}

\(update(rt,L,R,x):\)用\(x\)代表的线段更新最值

void update(int rt,int L,int R,int x){
	if(!t[rt]) return t[rt] = x,void();
	if(calc(x,mid) > calc(t[rt],mid)) swap(t[rt],x);
	//为什么让x线段始终处于下方：因为代码短(逃
	if(calc(x,L) > calc(t[rt],L)) update(lson,L,mid,x);
	if(calc(x,R) > calc(t[rt],R)) update(rson,mid + 1,R,x);
}

\(query(rt,L,R,pos):\)求所有与\(x=pos\)的交点的最大\(y\)值

一定是一路取\(max\)（标记永久化了）

db query(int rt,int L,int R,int pos){
    if(L == R) return calc(t[rt],pos);
    if(pos <= mid) return max(calc(t[rt],pos),query(lson,L,mid,pos));
    else return max(calc(t[rt],pos),query(rson,mid + 1,R,pos));
}

注意

1. 看看斜率范围，需不需要初始化
2. 询问或者更新的时候先判断当前是否有覆盖线段