hdu 5367 digger(动态线段树,区间合并)

题目链接

题意:

思路:线段树,要维护的域蛮多的。

下面高山脉简称”HM”

sum:区间中HM的总长度。

lsum,rsum,区间中包含左端点,右端点的高度相同的山的长度。

lh,rh:区间中包含左端点,包含右端点的的高度相同的山的高度。

llh,rrh:从左端点向右,从有段点向左的,第一个高度不相同的山的高度。

由于这道题n有1E9,没办法像以前的办法build 线段树,因此我们采用动态线段树的技巧。

官方题解:

对于求“高山脉”长度,可以利用线段树。树节点中保存左高度连续长度,左高度连续区间的高度,左高度连续区间的状态(即是否高于第一个高度不同的山),右高度连续长度,右高度连续区间的高度,右高度连续区间的状态,每段区间内的“高山脉”数量。每次更新时更新高度即可,在pushup过程中去计算新产生的“高山脉”。写起来难度不是很大,然后对于n很大且必须在线做这个条件只需对于线段树动态建立节点去维护即可

 

关于动态线段树:

平时我们做的线段树,假设区间为[1,n],那我们通常都是直接以 1 号点表示区间【1,n】,以 i*2 号点表示 i 节点代表区间的左半区间,以 i*2+1 号点表示 i 节点多代表区间的右半区间,一半空间长度都定义为4*n。
        在本题中,n比较大,直接将所有线段树中的所有节点定义出来不现实,那我们注意到,这道题实际上是对区间进行的一系列操作,那么就可能存在一个区间【l,r】,在所有处理过程中,该区间都可以被当做一个整体来看待。   如果是这样的话,我们定义出与该区间的子区间相对应的节点就没有意义了。
        动态生成线段树就是:假设对某一节点 p (代表区间【l,r】)进行处理时,并不是对整个区间[l,r]进行处理,而是对其某个子区间进行处理,那这个时候,该区间就不能一直被当做一个整体来看待,所以生成两个初始子节点lp、rp(节点之均为初始值),表示该区间的左半部分与右半部分,然后父节点 p 在对两个新生成的子节点进行更新。