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
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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Segment tree.
I want to learn Sparse table. Can you give me an idea using Sparse table?
Specially for calculating the subarray part.
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]