李超线段树

struct seg
{ld k,b; int id;seg(){k=0,b=0,id=0;}seg(ld k_,ld b_,int id_):k(k_),b(b_),id(id_){}ld f(int x){return k*x+b;}
};struct SGT
{
#define ls u << 1
#define rs u << 1 | 1
seg tag[N<<2];
bool cmp(seg x,seg y,int pos)
{if(x.f(pos) - y.f(pos) > eps) return 1;if(y.f(pos) - x.f(pos) > eps) return 0;return x.id < y.id;
}
void adt(int u,int l,int r,seg s)
{int mid = l + r >> 1;if(cmp(s,tag[u],mid)) std::swap(tag[u],s);if(cmp(s,tag[u],l)) adt(ls,l,mid,s);if(cmp(s,tag[u],r)) adt(rs,mid+1,r,s);
}
void down(int u,int l,int r)
{int mid = l + r >> 1;if(tag[u].id){adt(ls,l,mid,tag[u]);adt(rs,mid+1,r,tag[u]);tag[u] = seg(0,0,0);}
}
int qry(int u,int l,int r,int pos)
{if(l == r) return tag[u].id;int mid = l + r >> 1;down(u,l,r);if(pos <= mid) return qry(ls,l,mid,pos);else return qry(rs,mid+1,r,pos);
}
void upd(int u,int l,int r,int L,int R,seg s)
{if(L <= l && r <= R) {adt(u,l,r,s); return; }int mid = l + r >> 1;down(u,l,r);if(L <= mid) upd(ls,l,mid,L,R,s);if(R > mid) upd(rs,mid+1,r,L,R,s);
}
#undef ls
#undef rs
} t;