PROBLEM LINK:
Author:
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Segment Tree
PROBLEM:
Maintain a sequence of integers, and support the following operations:
- Modify one integer in the sequence.
- Find the maximum/sum of a given interval.
- Calculate the Longest Consecutive Non-Increasing/Non-Decreasing subintervals in a given interval.
EXPLANATION:
For the first two types of operations, they are very classical tasks for segment tree. Therefore, we mainly focus on how to deal with the last one type. Without loss of generality, we take the longest consecutive non-increasing subintervals as example.
First, build a segment tree on the sequence. In each node of segment tree, we record the following information:
- length is the length of the interval represented by this node.
- lv/rv is the leftmost/rightmost value of the interval represented by this node.
- LCNI is the longest consecutive non-increasing subintervals in the interval represented by this node.
- LCNI_L is the longest consecutive non-increasing subintervals in the interval represented by this node, but starting from the left end.
- LCNI_R is the longest consecutive non-increasing subintervals in the interval represented by this node, but ending at the right end.
To merge the information of node root from two children left and right in the segment tree, one can apply the following procedure:
root.LCNI = max(left.LCNI, right.LCNI)
if left.rv >= right.lv
root.LCNI = max(root.LCNI, left.LCNI_R + right.LCNI_L)
if left.LCNI_L == left.length && left.rv >= right.lv
root.LCNI_L = left.LCNI_L + right.LCNI_L
else
root.LCNI_L = left.LCNI_L
if right.LCNI_R == right.length && left.rv >= right.lv
root.LCNI_R = right.LCNI_R + left.LCNI_R
else
root.LCNI_R = right.LCNI_R
root.length = left.length + right.length
root.lv = left.lv
root.rv = right.rv
Therefore, all the queries could be answered in O(logN) time by using Segment Tree.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.
