LCIS问题与线段树区间合并

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

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

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

修改

对于修改函数,修改的关键在于Push-Up操作,也就是已经知道左右子树的l-len、r-len、c-len如何获得当前节点的l-len,r-len,c-len。

  • c-len:左右子树的c-len取最大,如果左右子树交接的地方连续(即满足$a_i < a_{i + 1}$),那么再与左子树的r-len加上右子树的l-len比大
  • l-len:如果左子树的l-len小于左子树的长度,那么直接等于左子树的l-len,否则要加上右子树的l-len
  • r-len:如果右子树的r-len小于右子树的长度,那么直接等于右子树的r-len,否则要加上左子树的r-len

查询

对于查询,我们定义查询函数query(o, l, r, L, R): int为查询$[L,R]$区间内的c-len,$[l,r]$是当前递归到的区间,我们取中点m = (l + r) >> 1,分三种情况讨论:

  • $R \leq m$,直接返回左子树的询问结果
  • $L > m$,直接返回右子树的查询结果
  • $L \leq m < R$,先求左右子树的最大的c-len,如果连续,则求左子树的r-len加右子树的l-len,比大

询问到区间包含的时候,直接返回区间c-len即可。

例题

题目链接:HDU – 3308

 

说点什么

avatar
50
  Subscribe  
提醒