hdu 3308 LCIS (线段树单点更新,区间合并)

题目链接

题意:长度为n的序列,单点更新,或者询问某一个区间中最长连续严格递增序列的长度是多少。(此处的连续为位置连续,并非数值连续,也就是3,5,7,9,这样的就是满足题意的长度为4的序列)

思路:线段树区间合并。维护三个域。

mx:区间中最长连续严格递增序列的长度

lm:包含区间左端点的最长连续严格递增序列的长度。

rm:包含区间右端点的最长连续严格递增序列的长度。

PushUp的时候,一个区间的答案显然可以从左右两个子区间的最大值得到。

还有一种可能是左右区间各取一部分,此时必须满足左区间的右端点值严格小于右区间的左端点值。

需要注意的是,如果某区间的最长连续严格递增子序列的长度等于区间长度,那么该区间可以向相应方向延伸。

查询的时候也是如此,要记得查询的时候,某一段区间对答案贡献不会超过区间长度。。

hdu有点坑。。。函数名不能命名为update…update2也不行2333

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz