Hi everyone, I'm trying to solve 316E3 - Summer Homework. Despite reading the tutorial link, I could't understand clearly the solution. Could you explain me more detail??
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.09.2026 01:12:08 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
The key is the merging step
While merging
and 
, we need to shift the Fibonacci multiplier of the second one by (l2 - r1) to the right , so that we get 
Shifting can be done by using identity Fn + m = FnFm - 1 + Fn + 1Fm
F[n+m+1] = F[n]*F[m-1] + F[n+1]*F[m] ??
Yes. Proof can be found from matrix exponentiation, or by induction here
Then make 2 segtree, for maintain
(supposed to be 
(supposed to be
seg1) andseg2).Sorry if this explanation seems unclear. More detail you can check my submission 7338693
wow, I've got it. Thanks you very much :)