[SOLVED] Finding a range satisfying a property in faster than linear time

Finding a range satisfying a property in faster than linear time

Given an array A[] we need to find a range which has the maximum size and its minimum element is >= 1. We also need to update this range by decreasing all its elements by 1.

One idea I got is to keep a segment tree for efficient updates. But how do I get the range in <= logarithmic time?

Maybe we can use binary search here.

Thanks

Solution

It's very interesting problem and I think it can be solved using Segment Tree.

Here are my idea (I hope it works fast enough):

For each segment, we need to store 4 info:

leftmost index of number < 1
rightmost index of number < 1
max size for this segment (store as range a and b)
lazy flag (true/false)

When we want to query max size, we can do recursive call to calculate the final answer. Assume our method was calcAnswer(left,right).

resA = calcAnswer(left, mid);

resB = calcAnswer(mid+1,right);

Max size will be max(resA.max_size, resB.max_size, combine(resA.right_index,resB.left_index)).

If the number of elements in array A[] are small (N<=50000), we can use Mo's Algorithm.