xyz_000's blog

By xyz_000, history, 6 years ago, In English

Please help with this problem from October circuit from Hackerearth. In their editorial they just posted solution code. Please provide some idea(I know that Segment tree can be used) but I am not sure how to handle the reverse operation.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This Problem helped me in solving this problem — GSS1

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Disclaimer: There may be multiple ways to solve this problem. Below I outline my approach during the contest.

Assuming that you can do basic stuff with segment trees, I suggest reading up this article: Answering max subarray range queries

Try the problem on your own for some time after reading up the article. If you don't make much progress, read up the hints in the order till you get to something new which you didn't think of earlier.

Hint #1
Hint #2
Hint #3