I was solving 446C - DZY любит числа Фибоначчи today where it's needed to add geometric sequence to the segment but the ratio is always the same. So I was wondering how to solve the problem where we are given queries of type $$$L,R,A,B$$$ and we need to add geometric sequence $$$A,AB,AB^2,AB^3,... AB^{R-L}$$$ to the segment $$$[L,R]$$$? There is also a sum query for some range.
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Anyone?
Does $$$O(n^{5/3} \log C)$$$ offline count xd
E: nvm, I don't even know how to do that.
Edit: I just wrote a bunch of text though but it is incorrect :/ my bad.
Just hold lazy vector of all your updates(ratio, range starting value) while also holding sum of lazy updates in lazy int, then when you need to push move all updates in vectors to child vectors while adding to childs lazy sums using formula for geo series, delete from current vector, and add lazy sum to main sum.
How do you merge the lazy updates of two different series with different ratios?
That's why you hold the updates in vectors on each node, and just hold the series sum in a lazy variable. That way you hardly have to think about merging them besides adding the updates to the lazy or sum variable. Fairly sure it is still amortized logn, but don't actually no time complexity, but I've used this trick multiple times.
Not sure I understand. If you make $$$N$$$ add queries of the form $$$1 \, N \, 1 \, B$$$ for different values of $$$B$$$ and then a query of "sum from $$$i$$$ to $$$i$$$" for every $$$i$$$ in $$$1 \ldots N$$$, how is it not $$$\Omega(N^2)$$$?
Hmm I think you're right actually rip. I guess I was just lucky it works for sparse data, but just to show I'm not making up I used it here's an example I actually used this and it somehow worked: link.