才刚刚开始/youl
线段树
最基础的线段树
首先是板子，维护最简单的信息以及懒标记的使用和下推（当然还有下推顺序）
对于最一般的线段树题（常规的维护序列信息）只要会 pushup 和 pushdown（后者仅仅在有懒标记的时候需要）就能使用线段树
pushup即将节点 (i) 的左右儿子信息合并成同等规模的 (i) 的信息，例如区间最大值的pushup即为 (maxval(i)=max(maxval(lson),maxval(rson)))
上面的板子的 pushup 和 pushdown 是最简单的一类
做线段树题需要三个要素
- 线段树节点上维护什么信息
- 如何将两个区间的信息合并成一个区间的信息
- 如果有懒标记，如何下推懒标记
用一道比较简单的例题来体会上面的流程
例1-洛谷P6492-STEP
维护全局最长的形如 LRLRLR 的子段长（即，不包含 LL 或者 RR 的最长子段）
考虑如果我们知道了 ([L,mid]) 和 ([mid+1,R]) 的信息，如何推出区间 ([L,R]) 的信息，也就是 ([L,R]) 的答案（最长子段）是怎么产生的
显然，([L,R]) 的最长子段只有 (3) 种情况
- 完全来源于 ([L,mid])
- 完全来源于 ([mid+1,R])
- 跨过 (mid) 的一段，也就是由 ([L,mid]) 的一段后缀和 ([mid+1,R]) 的一段前缀拼成
所以，为了得到 ([L,R]) 的答案
我们需要以下信息：
- ([L,mid]) 的答案和 ([mid+1,R]) 的答案（(ans_{[L,mid]}) 和 (ans_{[mid+1,R]})）
- ([L,mid]) 的最长合法后缀和 ([mid+1,R]) 的最长合法前缀（(suf_{[L,mid]}) 和 (pre_{[mid+1,R]})）
那么是不是 (ans_{[L,R]}=max(ans_{[L,mid]},ans_{[mid+1,R]},suf_{[L,mid]}+pre_{[mid+1,R]})) 呢
不完全是，因为 (suf_{[L,mid]}+pre_{[mid+1,R]}) 可能是 RLRL (+) LRLR 这样的，虽然本身都是合法的，但是不能拼在一起
所以还要额外记录 ([L,mid]) 的最右边字符以及 ([mid+1,R]) 的最左边字符，二者相异才能后缀拼前缀
三要素因为本题是单点修改变成了二要素
维护信息
线段树节点上维护该区间的最长合法子段长((ans_i))、最长合法前缀((pre_i))、最长合法后缀((suf_i))、最左边字符((lt_i))、最右边字符((rt_i))、区间长度((len_i))（区间长度是为了合并 (pre_i) 和 (suf_i)）
合并信息
void pushup(int i)
{
ans[i]=max(ans[ls],ans[rs]);
lt[i]=lt[ls],rt[i]=rt[rs];
pre[i]=pre[ls];
if(rt[ls]!=lt[rs])
{
if(pre[ls]==len[ls]) pre[i]+=pre[rs];//前缀可能越过mid
if(suf[rs]==len[rs]) suf[i]+=suf[ls];//后缀可能越过mid
ans[i]=max(ans[i],suf[ls]+pre[rs]);
}
return ;
}
练习题
洛谷P2894-Hotel-G
洛谷P2572-[SDOI2010] 序列操作
解决前缀最大值类问题-“楼房重建”型线段树
参考了小粉兔的博客
楼房重建
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
