Let array a1,...,an, ( 1<= n <= 10^6 )
3 kinds of quarries, m in total ( 1<= m <= 10^6 )
1 l r k: add k to al, ..., ar
2 l r k: change ai ( l<= i <=r ) in to max( ai , k )
3 l r: print max( al, ... ,ar )
I think it could be done it at mlogn by segment tree. How can I?
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Isn't this $$$\mathcal{O}(mn)$$$ anyway, if someone decides to just spam
3 1 nover and over and over again.You would have to print only the largest value, am I wrong?
Ah, forgive me, I horribly misread. I thought it asked to print all the elements in the range, which is quite stupid of me tbh.
Anyway, the comment of tfg should answer the question pretty well.
You're correct, you can do it better than quadratic. Read https://mirror.codeforces.com/blog/entry/57319, it's in there as task 2.