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

How to solve this Problem?
Автор It_was_a_nice_journey, история, 4 года назад, По-английски

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
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

Segment tree.

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

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

    Specially for calculating the subarray part.

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

      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]

      → Ответить