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??
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??
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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 :)