Mc_Square's blog

By Mc_Square, history, 2 months ago, In English,

A part of this Problem :

For every query range [L,R] (1 <= L<= R <= n) How to calculate maximum length subarray of 1 within segment [L,R].

1 <= n,query <= 100000

  • n = 10
  • [1, 9, 2, 3, 1, 1, 1, 4, 1, 1]
  • L = 3 , R = 10
  • answer = 3
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Segment tree.

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

    I want to learn Sparse table. Can you give me an idea using Sparse table?

    Specially for calculating the subarray part.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      My English is poor...

      But I will try my best.:)

      st[i][j]=1 if s[i]~s[i+(1<<j)-1] all equals to 1

      otherwise st[i][j]=0

      so if s[i]=1,st[i][0]=1

      and st[i][j]=st[i][j-1]&st[i+(1<<(j-1)][j-1]

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Thank you. I just've learnt about & operation in sparse table. But i can't understand the complexity when test case as:

        100000 100000

        1, 2, 1, 2, 1, 2, 1, 2, 1, 2,...........10^5th array element.(Repeating 1,2)

        query [L,R]

        1 10^5

        1 10^5

        1 10^5

        1 10^5

        .

        .

        .

        1 10^5th query.

        won't it get TLE if given 2 sec ? If not why??