Agassaa's blog

Help in segment tree problem
By Agassaa, 8 years ago, In English

The problem is: Given an array of 10^5 numbers and 10^5 queries, each query is like "i j" means: find the largest possible value A[y]-A[x] such that i<=x<=y<=j.

The analysis of this problem said it is easy to do with segment tree, but I have no idea, can anyone please explain how? (btw, it also has update operation, otherwise I could do it with offline semgment tree)

Thanks in advance!

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Link to the problem?

For a node in the segment tree keep : <min,max,answer>. Now think about how you would merge two nodes.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for each node keep: pair<min,max>

now the answer for each query is : quermax-quermin

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Spoiler

→ Reply