Tibor2007's blog

By Tibor2007, history, 5 weeks ago, In English

Hi,

I'm learning about segment trees at this moment. So I tried doing this exercise: https://codeforces.com/contest/356/problem/A. However, I didn't succeed. Unfortunately, the editorial doesn't mention the segment tree approach. Could someone explain how you would go about solving this with a segment tree.

Thanks

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Do each query in reverse, and then do the segment tree "set" operation.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

reverse the list of queries and then assign x to the range [l,x-1] and [x+1,r] (i.e don't change the value of ans[x] ).

You can check my submission using segment tree here. 127734288