Tibor2007's blog

Solving Knights tournament with a segment tree?
By Tibor2007, history, 3 years ago, In English

Hi,

I'm learning about segment trees at this moment. So I tried doing this exercise: https://mirror.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

Comments Comments (3)
| Write comment?
»
3 years 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

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

    Hey I am also stuck on the segment tree approach.Pls explain further, why reverse order and how did you visualize it as a segment tree?

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

      Hey, it is better to reverse it so the first queries override the last queries that don't really matter because you've already responded them. And the idea here is to use the lazy propagation segment tree(range updates).

      → Reply