Skip to main content
Computer Science

Return to Answer

I put in the range [l,l'] for the range-max query (which was not obvious).
Source Link
edit approved Jan 20, 2017 at 4:57
user64724
edit approved Jan 20, 2017 at 4:57
user64724
  • 55
  • 1
  • 5

You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, either $l<l'$ and $r<r'$ or $l>l'$ and $r>r'$. Now it's not hard to find the first interval $[l,r]$ s.t. $l\ge i$ and the last interval $[l',r']$ s.t. $r'\le j$, and a range-max of length array on the interval $[l, l']$ gives you the answer.

You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, either $l<l'$ and $r<r'$ or $l>l'$ and $r>r'$. Now it's not hard to find the first interval $[l,r]$ s.t. $l\ge i$ and the last interval $[l',r']$ s.t. $r'\le j$, and a range-max of length array gives you the answer.

You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, either $l<l'$ and $r<r'$ or $l>l'$ and $r>r'$. Now it's not hard to find the first interval $[l,r]$ s.t. $l\ge i$ and the last interval $[l',r']$ s.t. $r'\le j$, and a range-max of length array on the interval $[l, l']$ gives you the answer.

Source Link
aaaaajack
aaaaajack
  • 515
  • 2
  • 7

You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, either $l<l'$ and $r<r'$ or $l>l'$ and $r>r'$. Now it's not hard to find the first interval $[l,r]$ s.t. $l\ge i$ and the last interval $[l',r']$ s.t. $r'\le j$, and a range-max of length array gives you the answer.