LCIS问题与线段树区间合并

维护区间最长连续上升序列(LCIS)问题是线段树区间合并的典型例题,本文是这类算法的学习笔记。

为了维护区间最长连续上升序列,我们需要对于线段树上的每个区间$[l,r]$,我们需要维护一个左端点为起点的最长连续区间$[l,u]$长度l-len,维护一个右端点为终点的最长连续区间$[v, r]$长度r-len,同时维护一个中间的最长连续区间$[x, y]$长度c-len,这个区间可能穿越中点,也可能不穿越中点,可能包含左右端点,也可能不包含左右端点。维护的这些区间都满足LCIS的性质。

对于动态维护,关注如何修改和如何查询。

继续阅读