I have heard about segment trees that can handle delete queries by processing the queries offline and creating a segment tree over the timeline of the queries. Does anyone know about this? (It could be persistent segment tree, but i'm not sure. If the structure above does not exist, please tell me.)
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:54:16
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
29:54:16
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 11:40:45 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
please give the link of the original problem
the editorial uses sqrt decomposition to solve the problem, and i can't just check all submissions, but all submissions i saw used the sqrt method too
... but i still don't know which problem you're referring to
You need to be more clear about what operations the data structure has to support. If you need it to support the deletion of intervals among many other queries and updates that necessitate a segment tree, then a treap (with merge and split operations) is your best bet.
Seams like you are talking about this trick: https://usaco.guide/adv/offline-del?lang=cpp