思路:
首先, 由题意可以看出, 需要寻找的是从第一个有值的点开始的最长的斜率严格递增的序列长度.
考虑使用线段树解决, 询问的答案即为根节点的值, 同时修改只有单点修改, 所以只需要考虑区间的合并.
至于合并, 假设每个区间都储存了一个序列:
该序列是只考虑该区间时的最长递增序列.
首先左区间序列里的所有值都是可见的, 而右区间只有比左区间最大值更大的值才可见. 这些值在右区间序列是连续的.
若右区间长度为1则直接判断返回即可, 否则将右区间分为两段(称为左右区间和右右区间). 然后分类讨论:
若左右区间的最大值小于等于左区间的最大值, 说明可见的分界点在右右区间中, 递归到右右区间寻找.
否则说明分界点在左右区间中, 右右区间中在右区间序列中的值均可见, 统计上该部分值后递归到左区间寻找.
这样便在O(log n)的时间内实现了区间的合并.
代码:
1 |
|