Блог пользователя Tibor2007

Solving Knights tournament with a segment tree?
Автор Tibor2007, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

      → Ответить