首页 > 其他分享 >李超线段树

李超线段树

时间:2024-02-15 10:45:10浏览次数:34  
标签:return int mid 线段 李超 id num ll

李超线段树

线段树的扩展版本

用来动态维护平面上直线

支持插入直线/线段,查询横坐标某处覆盖的线中纵坐标最大/最小值

可以用于斜率优化 DP

插入直线

这里直线是线段树上维护的信息,表示当前区间中点处最优的直线

同时相当于区间修改,直线也是标记,这个区间内都可能有这条直线

但是标记难以合并,必须递归下传

有时两条直线在区间的中间产生交点,无法确定子节点需要哪个

因此利用标记永久化的思想,只有在当前区间中点不优且可能成为子节点区间中点更优的直线才下传,每个节点上存的直线不一定是当前在它中点处最优的,但是如果有更优的,一定会在根节点到它路径上某处被记录

假设在 \([l,r]\) 中点 \(mid\) 处原有直线 \(x\) 更优,新增直线为 \(y\),如果相反则交换 \(x,y\)

  • 如果 \(l,r\) 处 \(x\) 都比 \(y\) 优,\(y\) 在整个区间内不可能比 \(x\) 优,直接返回
  • 如果 \(l\) 处 \(y\) 更优,则递归至 \([l,mid]\),如果 \(r\) 处 \(y\) 更优,则递归至 \([mid+1,r]\)

因为插入的是直线,第二种情况中只会有一个成立,最多递归一边,复杂度是 \(O(\log n)\) 的

插入线段

由于线段只在某一区间内生效,因此需分成 \(O(\log n)\) 个区间,每个区间都递归下传,复杂度为 \(O(\log^2n)\)

查询

比较简单,直接找到那个点,注意要一路比较取最优的

P4097 【模板】李超线段树 / [HEOI2013] Segment

struct seg
{
	double k, b;	int id; 
}lin[M];
double calc(int x, int p)	{return lin[p].k * x + lin[p].b;}
int chkmax(int x, int p, int q) // 点 x 处 p,q 哪条直线取值更优
{
	if(!p || !q)	return p + q; 
	double val1 = calc(x, p), val2 = calc(x, q);
	return sgn(val1 - val2) > 0 ? p : (sgn(val1 - val2) < 0 ? q : (lin[p].id > lin[q].id ? q : p)); 
}
struct lctree
{
	int num[N << 2];
	int lson(int x)	{return x << 1;}
	int rson(int x)	{return x << 1 | 1;}
	void upd(int l, int r, int p, int x) // 递归下传
	{
		if(l == r)	{num[p] = chkmax(l, num[p], x);	return;}
		int mid = (l + r) >> 1;
		if(chkmax(mid, num[p], x) == x)	swap(num[p], x);
		if(chkmax(l, num[p], x) == x)	upd(l, mid, lson(p), x);
		if(chkmax(r, num[p], x) == x)	upd(mid + 1, r, rson(p), x);
	}
	void update(int l, int r, int nl, int nr, int p, int x) // 拆分线段
	{
		if(l <= nl && nr <= r)	return upd(nl, nr, p, x);
		int mid = (nl + nr) >> 1;
		if(mid >= l)	update(l, r, nl, mid, lson(p), x);
		if(mid < r)	update(l, r, mid + 1, nr, rson(p), x);
	}
	int query(int id, int l, int r, int p)
	{
		if(l == r)	return num[p];
		int mid = (l + r) >> 1, res = num[p];
		if(mid >= id)	return chkmax(id, res, query(id, l, mid, lson(p)));
		return chkmax(id, res, query(id, mid + 1, r, rson(p)));
	}
}tree;

线段树合并

李超树也可以合并!

按正常线段树合并的流程,合并叶子就直接取最优的,注意合并后要把另一棵线段树上对应节点的直线当作标记下传更新

复杂度有大佬说时 \(O(n\log n)\) 的,用了势能证明,我不会

应用

斜率优化

CF932F Escape Through Leaf

DP 方程不难列出:

\[f_i=\min_{j\in subtree_i}\{f_j+a_i\times b_j\} \]

有 \(i,j\) 的乘积项,看着很斜率优化,如果把 \(f_j\) 当作 \(b\),\(b_j\) 当作 \(k\),\(a_i\) 当作 \(x\),\(f_i\) 当作 \(y\)

则式子是 \(y=kx+b\) 的形式,用李超线段树插入直线,维护最小值

但是 \(j\) 必须在 \(i\) 子树内,可以用李超线段树合并,复杂度为 \(O(n\log n)\),还可以用 DSU on tree,复杂度为 \(O(n\log^2n)\)

ll calc(ll id, ll x)	{return id ? (x - D) * lin[id].k + lin[id].b : inf;} 
struct lctree
{
	ll ls[N * 20], rs[N * 20], num[N * 20], idx; // 动态开点
	ll update(ll l, ll r, ll p, ll id)
	{
		if(!p)	p = ++idx;
		if(!num[p])	{num[p] = id;	return p;}
		ll mid = (l + r) >> 1;
		if(calc(id, mid) < calc(num[p], mid))	swap(num[p], id);
		if(calc(num[p], l) > calc(id, l))	ls[p] = update(l, mid, ls[p], id);
		if(calc(num[p], r) > calc(id, r))	rs[p] = update(mid + 1, r, rs[p], id);
		return p;
	}
	ll merge(ll x, ll y, ll l, ll r)
	{
		if(!x || !y)	return x + y;
		if(l == r)	return calc(num[x], l) > calc(num[y], l) ? y : x; 
		ll mid = (l + r) >> 1;
		ls[x] = merge(ls[x], ls[y], l, mid);
		rs[x] = merge(rs[x], rs[y], mid + 1, r);	
		return update(l, r, x, num[y]); // 注意下传!
	}
	ll query(ll x, ll l, ll r, ll p)
	{
		if(!p)	return inf;
		ll res = calc(num[p], x);
		if(l == r)	return res;
		ll mid = (l + r) >> 1;
		if(mid >= x)	return min(res, query(x, l, mid, ls[p]));
		return min(res, query(x, mid + 1, r, rs[p]));
	}
}tree;
void dfs(ll x, ll fa)
{
	for(ll y : edge[x])
		if(y != fa)	dfs(y, x), root[x] = tree.merge(root[x], root[y], 0, V);
	if(root[x])	f[x] = tree.query(a[x] + D, 0, V, root[x]);
	lin[++cnt] = (line){b[x], f[x]};
	root[x] = tree.update(0, V, root[x], cnt);
}
int main()
{
	read(n);
	for(ll i = 1; i <= n; ++i)	read(a[i]);
	for(ll i = 1; i <= n; ++i)	read(b[i]);
	for(ll i = 1; i < n; ++i)	read(u), read(v), edge[u].pb(v), edge[v].pb(u);
	dfs(1, 0);
	for(ll i = 1; i <= n; ++i)	print(f[i]), putchar(' ');
	return 0;
}

标签:return,int,mid,线段,李超,id,num,ll
From: https://www.cnblogs.com/KellyWLJ/p/18016006

相关文章

  • 2024.2.14 WC24 线段树 / CF1572D / lgP3679
    西安Day1。感冒还没好,牙龈炎也没好,明天还要考试,又要坐牢了/kk。今天是tyy的图论选讲,感觉前面网络流部分还是在线的,平面图部分毒瘤tyy拿出了他的员交课件,恐怖,直接下线了。看了NAVI和Faze的预选赛,你们俩怎么都打的这么稀碎/fn。Override真好听。「WC2024」线段树我......
  • 线段树分治学习笔记
    线段树分治线段树分治是一种可以离线处理带撤销问题的常用手段。一般而言,题目中加入操作很好维护,但删除操作不好维护,这时可以对时间维建线段树,把每一个操作加入其存在时间段对应的线段树节点上,然后处理所有询问,进入一个节点时将这个节点里的操作加入,递归左右儿子,然后撤销这一次做......
  • 李超树
    李超树(不得不抱怨一下我现在正在用的这个键盘,好难打,如果有啥子笔误请指出)基础支持在线插入一条线段,一条直线,插入线段的极限时间复杂度是\(O(log^2)\),插入一条直线的时间复杂度是\(O(log)\)的。支持查询一个已知\(x\)的竖线与插入的直线段的交点的最值。实现与普通线段树......
  • 线段树进阶奇淫巧计
    看本文文字部分可以少带脑子,但是代码部分仔细看了因为不一定编译了不一定对动态开点一般来说线段树的空间开销是比较巨大的,需要\(4n\)的空间,一般其实是可以支撑的,但是权值线段树就不一定了。值域级别的代价是支持不了的。一般在动态开点的前提下只需要支持单点操作一旦是序......
  • 线段树
    3.区间操作与Lazy-Tag本节介绍线段树的核心操作Lazy-Tag,并给出区间修改\(+\)区间查询的模板。在线段树上,如果直接进行区间修改,时间复杂度为\(\mathcal{O}(N\logN)\)。而Lazy-Tag可以将其降为\(\mathcal{O}(\logN)\)。Lazy-Tag方法用\(lz_p\)统一记录区间\(p......
  • 线段树维护字符串哈希
    [ABC331F]PalindromeQuery#include<bits/stdc++.h>usingnamespacestd;#defineendl"\n"#defineintlonglongtypedeflonglongll;constintbase=131;constintp1=1222827239;constintN=1e6+100;intn,q,pn[N];strings......
  • 楼房重建线段树
    维护前缀最大值个数。对pushup操作进行修改。定义solve(x,lim)为前面这个区间的最大值为lim,\(x\)支配的区间产生的贡献。如果\(x\)的最大值已经小于\(lim\),显然没有贡献。考虑\(x\)的左儿子,如果左儿子的最大值大于\(lim\)直接递归左二子查询,此时右儿子的答案不......
  • P6025 线段树 题解
    解题思路暴力做法从\(l\)到\(r\)枚举每一个数,然后建线段树,记录最大下标,然后计算答案。代码略。时间\(O(n^2)\),期望得分:\(10\)分。优化暴力我们考虑每次枚举不遍历整棵线段树。显然,贪心的,最深的最右边的节点编号最大。那么我们可以发现,如果两颗子树大小相同,那么最大节......
  • P10145 [WC/CTS2024] 线段树 题解
    Link纪念一下场切题。题意:给定一棵(分点不一定为中点)的线段树,给定若干个询问区间,问有多少个线段树上结点的集合,知道了这些结点对应的区间和就可以知道任何一个询问区间的和。从询问区间开始考虑。会发现可以把所有\(a_i\)分成若干个集合,只要知道每个集合的和就可以知道所有询......
  • 洛谷 P10145 [WC/CTS2024] 线段树 题解--zhengjun
    提供一种考场做法,在思路上和官方题解的差异蛮大的,虽然结果差不多。首先需要发现\([l,r)\)区间可以算出来的充要条件是:如果对于每个选中的节点\(u\),连无向边\((L_u,R_u)\),则当且仅当\(l\)和\(r\)连通时区间\([l,r)\)可以算出来。证明的话,用前缀和理解这些东西,分别考虑......