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
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
13:43:35
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
13:43:35
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 03:51:27 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
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