你会写李超树吗?
查看原帖
你会写李超树吗?
223298
do_while_true楼主2022/6/26 23:03

今年的早些时候,年轻的 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,欢迎大家来学习和交流!

2022/6/26 23:03
加载中...