L_H's blog

Spoj GSS1
By L_H, 9 years ago, In English

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)

  • Vote: I like it
  • -11
  • Vote: I do not like it

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

Here is my approach with complexity.

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

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

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

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

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

        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.

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

Here

→ Reply