Hello every one... I need a data structure handling two type of queries. 1. Maximize(l,r,x) 2. Sum(l,r)
I have a O(sqrt(n)*log(n)) solution using sqrt decomposition + set.But I am looking for a better solution. Thanks in advance
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.11.2024 10:14:50 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by Shayan.P (previous revision, new revision, compare).
Maximise (l,r,x) means set a[i] = max(a[i], x) ?
Segment tree beats.
It was awesome. Thank you!
Btw do you have any link to Chinese trick like this?
It's possible sqrt decomposition in this case without logarithmic factor? (Lazy sqrt decomposition or dsu approach? Yeah... segment tree beats is cool)
By setting a proper bucket size, you can achieve
per query.
Yeah, I know...,but with potential function analyze (7'-'). u.u maybe, I hope :v