It_was_a_nice_journey's blog

How to solve this Problem?
By It_was_a_nice_journey, history, 5 years 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

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

Segment tree.

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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]

      → Reply