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

Spoj GSS1
Автор L_H, 10 лет назад, По-английски

Hello friends I am trying to solve http://www.spoj.com/problems/GSS1/ but I am a little weak in segment trees So I am not able to figure out How my preprocessing function will look like and also If someone could explain a way to solve this without segment trees (as there are only queries no updation required)

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

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

Here is my approach with complexity.

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

    Can't we do it in O(NlogN) by using sparse table algorithm?

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

      Well, i think there is no difference between sparse table and segment tree for this problem, except memory ability. If one figured out how to merge two constructive part he would think about doing it via segment tree with O(N) memory.

      But above approach is completely different from those two(segment tree and sparse table).

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

        Thanks for your reply. I had a doubt in the sparse table implementation. Once we have pre-processed the values,in the query function we'll have to use the binary representation of j-i to calculate F[i][j], right? I have worked out a solution.I was wondering if this approach is correct.

        This is my code, http://ideone.com/kw0T2S

        I am implementing segment tree/sparse table algorithm for the first time,so kindly help me out.

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

Here

→ Ответить