17.CF739C Alyona and towers 区间合并线段树

17.CF739C Alyona and towers 区间合并线段树

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定序列，要求支持区间加，以及查询最长先增后减子区间(单峰序列)长度

非常典型的区间合并线段树，记录左右起LIS，LCS，单峰

洛谷传送门：CF739C Alyona and towers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：Problem - 739C - Codeforces

题目分析

CSDN的SVG图像显示可能有点问题？

给定序列，要求支持区间加，以及查询最长先增后减子区间(单峰序列)长度。

区间和并线段树，我们需要记录每个区间的最大的左端点起 L I S LIS LIS长度( l l i s llis llis)、左端点起 L D S LDS LDS长度( l l d s llds llds)、右端点结束 L I S LIS LIS长度( r l i s rlis rlis)、右端点结束 L D S LDS LDS长度( r l d s rlds rlds)、左端点起单峰长度 P L M ( p l m ) PLM(plm) PLM(plm)、右端点起单峰长度 P R M ( p r m ) PRM(prm) PRM(prm)，无限制单峰长度 A N S ( a n s ) ANS(ans) ANS(ans)，以及左右端点 l v , r v lv, rv lv,rv。

考虑合并的方式：对于两个区间，在合并的方式，容易想到端点的关系决定了合并后的结果：

我们首先需要对合并的结果进行初始化，我们设合并后的信息为 r e s res res，加号右侧信息(就是右区间) x x x，则：

res.lv = lv, res.rv = x.rv;
res.llis = llis, res.llds = llds;
res.rlis = x.rlis, res.rlds = x.rlds;
res.plm = plm, res.prm = x.prm;
res.ans = max(ans, x.ans);
res.len = len + x.len;

1. 左区间右端点值 < < > >右区间左端点值时，我们对 L D S LDS LDS和单峰、答案采取类似的方式进行合并即可。

综上所述，我们可以得到区间合并信息的过程：

struct info{
    int lv = 0, rv = 0;
    int ans = 1, llis = 1, llds = 1, rlis = 1, rlds = 1, plm = 1, prm = 1, len = 1;
    info() {}
    info(int val): lv(val), rv(val) {}
    info operator+ (info &x) {
        info res;
        res.lv = lv, res.rv = x.rv, res.ans = max(ans, x.ans);
        res.llis = llis, res.llds = llds;
        res.rlis = x.rlis, res.rlds = x.rlds;
        res.plm = plm, res.prm = x.prm;
        res.len = len + x.len;
        if(rv  x.lv){
            if(llds == len) res.llds += x.llds;
            if(x.rlds == x.len) res.rlds += rlds;
            if(plm == len) res.plm += x.llds;
            if(x.rlds == x.len) res.prm = max(res.prm, x.len + prm);
            res.ans = max(res.ans, prm + x.llds);
        }
        return res;
    }
}tree[N