Indian Computing Olympiad

Range Queries→Longest open segment

There are N plots arranged in a sequence 1..N. As time goes by, these plots are sold, one at a time. Periodically, you have to report the longest unsold segment of plots.

For instance, if N = 15 and you get the instructions

  sell(3)
  sell(8)
  sell(7)
  sell(15)
  report()
      

the answer is 6, which is the length of the empty interval [9,14].

Construct a segment tree whose leaves correspond to the plots. For each interval I, maintain:

  longest(I)      :  length of longest open segment in I
  longestleft(I)  :  distance to first sold plot from left end of I
  longestright(I) :  distance to first sold plot from right end of I
      

The final answer we want is longest([1..N])

When we sell a plot, we have to update these four quantities.

  // longest(I) is either max longest from left or right, or spans the
  // two subintervals
  longest(I) = max(longest(left(I)),
                   longest(right(I),
                   longestright(left(I)) + longestleft(right(I)))

  // longestleft(I) is longestleft(left(I)) unless entire left interval
  // is empty, which is checked by asking if longestleft(left(I)) is
  // equal to length(left(I))
  longestleft(I) = if longestleft(left(I)) = length(left(I))
                   then
                     length(left(I)) + longestleft(right(I))
                   else
                     longestleft(left(I))

  // symmetric computation for longestright(I)
  longestright(I) = if longestright(right(I)) = length(right(I))
                    then
                      length(right(I)) + longestright(left(I))
                    else
                      longestright(right(I))
      

Exercise: What if we can demolish houses and restore a plot to being empty?

---