CF739CAlyonaandtowers解题报告

线段树绝世好题。

题意：

维护区间加，全局最长单峰序列。

Solution：

维护 \(8\) 个量。

\(lval\)：左端点的权值。

\(rval\)：右端点的权值。

\(lmax\)：以左端点开始的最长的下降序列长度。

\(rmax\)：以右端点结束的最长的上升序列长度。

\(lans\)：以左端点开始的最长的单峰序列长度。

\(rans\)：以右端点结束的最长的单峰序列长度。

\(ans\)： 区间内最长的单峰序列长度。

\(tag\)：区间加法懒标记。

考虑怎么用左右两个儿子更新父节点的信息。

用 \(lson\) 来表示左儿子，\(rson\) 来表示右儿子，\(rt\) 来表示父节点。

\(lval\)

显然父节点的 \(lval\) 是左儿子的 \(lval\)。

\(rval\)

显然父节点的 \(rval\) 是右儿子的 \(rval\)。

\(lmax\)

如果说左儿子的 \(lmax\) 等于左儿子的区间长度，说明了左区间是个下降区间，如果同时左儿子的 \(rval\) 大于了右儿子的 \(lval\) 说明了父节点的 \(lmax\) 能向右区间伸展，这个时候 \(rt.lmax = lson.lmax + rson.lmax\)。

否则无法跨过右区间，直接继承左儿子的值：\(rt.lmax = lson.lmax\)。

\(rmax\)

如果说右儿子的 \(rmax\) 等于右儿子的区间长度，说明了右区间是个上升区间，如果同时左儿子的 \(rval\) 小于了右儿子的 \(lval\) 说明了父节点的 \(rmax\) 能向左区间伸展，这个时候 \(rt.rmax = lson.rmax + rson.rmax\)。

否则无法跨过左区间，直接继承右儿子的值： \(rt.rmax = rson.rmax\)。

\(lans\)

如果说左儿子的 \(rmax\) 等于左儿子的区间长度，说明了左儿子是个上升区间。

这个时候分两种情况：

• \(lson.rval 说明了还能通过右儿子的 \(lans\) 继续扩展：\(rt.lans = lson.rmax + rson.lans\)。

-\(lson.rval > rson.lval\) 说明了只能通过右儿子的 \(lmax\) 继续扩展： \(rt.lans = lson.rmax + rson.lmax\)。

如果说左儿子的 \(lans\) 等于区间长度，想用右儿子扩展的话，必须满足 \(lson.rval > rson.lval\)，这个时候：\(rt.lans = lson.lans + rson.lmax\)。

否则无法通过右区间来更新，直接继承左儿子的值：\(rt.lans = lson.lans\)。

\(rans\)

如果说右儿子的 \(lmax\) 等于右儿子的区间长度，说明了右儿子是个下降区间。

这个时候分两种情况：

• \(lson.rval > rson.lval\) 说明了还能通过左儿子的 \(rans\) 继续扩展：\(rt.rans = lson.rans + rson.lmax\)。

  
  



• \(lson.rval 说明了只能通过左儿子的 \(rmax\) 继续扩展： \(rt.rans = lson.rmax + rson.lmax\)。

  
  

如果说右儿子的 \(lans\) 等于区间长度，想用左儿子扩展的话，必须满足 \(lson.rval ，这个时候：\(rt.rans = lson.rmax + rson.lans\)。

否则无法通过右区间来更新，直接继承左儿子的值：\(rt.rans = rson.rans\)。