Здравствуйте. Я ищу какие-нибудь задачи на переливания (то есть когда в динамике по поддеревьям сливаются два множества, и если переливать большее в меньшее, то общее количество операций будет $$$O(nlogn)$$$ ). Если кто-нибудь знает такие задачи, напишите о них в комментариях, пожалуйста.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.04.2024 00:28:40 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been translated by Dannypa (original revision, translated revision, compare)
You can see the "dsu"-taged problems.
Thanks for narrowing the search space down to a couple hundreds
If your "set" means
std::setor any self balancing tree, the total time complexity is $$$\mathcal{O}(n\log^2n)$$$, not $$$\mathcal{O}(n\log n)$$$.Why the downvotes smh
The technique is called "small to large" you will find some problems here
I thnk OP also meant small to large but just to be clear, the complexity is actually $$$\mathcal{O}(nlog^2n)$$$
There are many ways to store a set. One of them is
std::unordered_set, which has $$$O(1)$$$ insertion and $$$O(size)$$$ traversal, which yields $$$O(n\log n)$$$ total time for some problems. So, the "small to large" idea is not tied to a certain complexity.Also, sometimes we are allowed to store duplicates (or we can prove that there are no duplicates). Then, we can store sets in linked lists and merge two of them in just $$$O(1)$$$. This wouldn't require "small to large" then, but I've seen at least one problem in this comment section, which can be solved this way.
Thanks!
Great! This list is helpful.
Can you share more lists of other topics? would be more helpful :)
link
credits: Abdelrhman_Akram
https://codeforces.com/blog/entry/44351 в конце есть задачи
Спасибо!
https://usaco.guide/plat/merging?lang=cpp
https://codeforces.com/contest/1620/problem/E This one
It is called Small to Large technique.
Problem.