The problem asks as to handle 2 queries: 1.Update a value to h 2.Ask the maximum distance you can walk while not going to adjacent points with absolute value>h
We can use segment_tree to maintain the max absolute value in a segment.First,build the segtree(you don't need to use lazy tags). For query1,use single-point update in a segtree.Time complexity:O(log n) For query2,lets assume we're finding about this query:(2,ident,height).Use binary search to find out the minimum and maximum place you can go.Divide that into 2 steps:
Set le to 1 and ri to ident.each time,mi=(le+ri)/2.If the max abs value in [mi,ident] <=height,then set ri to mi,otherwise set le to mi+1.
Set le to ident and ri to n.Each time,mi=(le+ri+1)/2.If the max abs value in [ident,mi] <=height,then set le to mi,otherwise set ri to mi-1.
Any problems?Reply in comments!