do_while_true @ 2022-06-26 23:03:31
今年的早些时候，年轻的 dwt（do_while_true） 正照常水群。
他看见 LA 群里强大的 George1123 正在吐槽早些时候写的臃肿题解，举了李超树的例子。
dwt 定睛一看，怎么李超树还有如此简洁的写法？他翻了 oi-wiki，翻了洛谷题解区，竟然都是 dwt 年少懵懂时所写的巨型分类讨论：
举例（来自我 21 年 4 月的提交记录）：
void modify(int x, int cl, int cr, int l, int r, int u) {
int v = tree[x].s, mid = (cl + cr) >> 1;
if(r < cl || cr < l) return ;
ld yu = calc(u, mid), yv = calc(v, mid);
if(l <= cl && cr <= r) {
if(cl == cr) {
if(yu > yv) tree[x].s = u;
return ;
}
if(li[v].k < li[u].k) {
if(yu > yv) {
tree[x].s = u;
modify(ls, cl, mid, l, r, v);
}
else modify(rs, mid+1, cr, l, r, u);
}
else if(li[v].k > li[u].k) {
if(yu > yv) {
tree[x].s = u;
modify(rs, mid+1, cr, l, r, v);
}
else modify(ls, cl, mid, l, r, u);
}
else if(li[u].b > li[v].b) tree[x].s = u;
return ;
}
modify(ls, cl, mid, l, r, u);
modify(rs, mid+1, cr, l, r, u);
}他从未发现李超树竟然如此好写，于是费尽千辛万苦学会了李超树的简洁写法，现在它已经全面上线 oi-wiki，欢迎大家来学习和交流！
by NujObIuc @ 2022-06-26 23:11:17
@do_while_true 我感觉 panyf 的李超树代码是我最喜欢的，短小而精悍！
https://www.luogu.com.cn/blog/221955/solution-cf1175g
by do_while_true @ 2022-06-26 23:13:44
@ZCPB 其实你仔细看看，oi-wiki中的示例代码和 panyf 写的差不多，只不过他是全局插入（插入直线）所以少了一个函数！
by do_while_true @ 2022-06-26 23:15:01
他的代码压行稍微多一点，逻辑上是一样的？
by NujObIuc @ 2022-06-26 23:15:56
@do_while_true 道理都一样，但是 panyf 我感觉是迄今为止我见过最短的，感觉给人看起来非常的舒适。
by MC小萌新 @ 2022-06-26 23:18:03
我之前就照着 oiwiki 学的，代码和它差不多长/qd
by wkywkywky @ 2022-06-26 23:21:29
然而这并不巨型(
by 听取MLE声一片 @ 2022-06-26 23:22:08
巨型
by wkywkywky @ 2022-06-26 23:23:00
wky的分讨写法
void update(int rt,int ul,int ur,d uk,d ub,int uid){
int l=tr[rt].l,r=tr[rt].r;
int mid=(l+r)>>1;
if(ul<=l&&r<=ur){
d ue=((d)r-(d)l)*uk+ub;
d te=((d)r-(d)l)*tr[rt].k+tr[rt].b;
if(tr[rt].f==0){
tr[rt].f=1;
tr[rt].k=uk;tr[rt].b=ub;tr[rt].id=uid;
}
else {
if(ub-tr[rt].b>eps&&ue-te>eps){
tr[rt].k=uk;tr[rt].b=ub;tr[rt].id=uid;
}
else {
if(ub-tr[rt].b<-eps&&ue-te<-eps)return;
if(ub-tr[rt].b<-eps&&abs(ue-te)<eps)return;
if(abs(ub-tr[rt].b)<eps&&ue-te<-eps)return;
else {
d um=((d)mid-(d)l)*uk+ub;
d tm=((d)mid-(d)l)*tr[rt].k+tr[rt].b;
if(ub-tr[rt].b>eps){
if(um-tm>eps){
update(rt*2+1,mid+1,r,tr[rt].k,tm+tr[rt].k,tr[rt].id);
tr[rt].k=uk;tr[rt].b=ub;tr[rt].id=uid;
}
else {
update(rt*2,ul,mid,uk,ub,uid);
}
}
else {
if(um-tm>eps){
update(rt*2,l,mid,tr[rt].k,tr[rt].b,tr[rt].id);
tr[rt].k=uk;tr[rt].b=ub;tr[rt].id=uid;
}
else {
update(rt*2+1,mid+1,ur,uk,um+uk,uid);
}
}
}
}
}
return;
}
if(ul<=mid)update(rt*2,ul,ur,uk,ub,uid);
if(ur>mid){
if(ul>mid)update(rt*2+1,ul,ur,uk,ub,uid);
else update(rt*2+1,mid+1,ur,uk,ub+((d)mid+(d)1-(d)ul)*uk,uid);
}
}by wkywkywky @ 2022-06-26 23:25:45
什么叫重工业啊（战术后仰）
by hellomath @ 2022-06-26 23:26:01
我的：
struct line {
ll k, b;
ll operator () (ll x) { return k * x + b; }
} t[maxn << 2];
void ins(int k, int l, int r, line a) {
if (t[k](mid) < a(mid)) swap(t[k], a);
if (l == r) return;
t[k].k > a.k ? ins(ls, l, mid, a) : ins(rs, mid + 1, r, a);
}
ll qmax(int k, int l, int r, int v) {
if (l == r) return t[k](v);
return max(t[k](v), mid >= v ? qmax(ls, l, mid, v) : qmax(rs, mid + 1, r, v));
}