ACM14KN4 - Editorial

PROBLEM LINK:

Practice
Contest

Author:
Tester: Jingbo Shang
Editorialist: Jingbo Shang

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Segment Tree

PROBLEM:

Maintain a sequence of integers, and support the following operations:

  1. Modify one integer in the sequence.
  2. Find the maximum/sum of a given interval.
  3. 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:

  1. length is the length of the interval represented by this node.
  2. lv/rv is the leftmost/rightmost value of the interval represented by this node.
  3. LCNI is the longest consecutive non-increasing subintervals in the interval represented by this node.
  4. LCNI_L is the longest consecutive non-increasing subintervals in the interval represented by this node, but starting from the left end.
  5. 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.

2 Likes

here is my code, i am getting WA… plz help

It seems that you misunderstood the operation I and D. It is not a boolean query, it is a numerical. Please check the problem statements in the editorial and original description. Thanks!

Does any body notify that the practice and contest links are redirecting to two different problems…:slight_smile:

1 Like

Shouldn’t the code root.LCNI_L = left.LCNI_L

be root.LCNI_L = max(left.LCNI_L,right.LCNI_L)?

//