Блог пользователя Dannypa

Задачи на переливания?
Автор Dannypa, история, 2 года назад, По-русски

Здравствуйте. Я ищу какие-нибудь задачи на переливания (то есть когда в динамике по поддеревьям сливаются два множества, и если переливать большее в меньшее, то общее количество операций будет $$$O(nlogn)$$$ ). Если кто-нибудь знает такие задачи, напишите о них в комментариях, пожалуйста.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been translated by Dannypa (original revision, translated revision, compare)

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

You can see the "dsu"-taged problems.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

If your "set" means std::set or any self balancing tree, the total time complexity is $$$\mathcal{O}(n\log^2n)$$$, not $$$\mathcal{O}(n\log n)$$$.

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

The technique is called "small to large" you will find some problems here

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I thnk OP also meant small to large but just to be clear, the complexity is actually $$$\mathcal{O}(nlog^2n)$$$

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks!

    → Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Great! This list is helpful.

    Can you share more lists of other topics? would be more helpful :)

    → Ответить
»
2 года назад, # |
← Rev. 9   Проголосовать: нравится +11 Проголосовать: не нравится

https://codeforces.net/blog/entry/44351 в конце есть задачи

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

https://usaco.guide/plat/merging?lang=cpp

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

https://codeforces.net/contest/1620/problem/E This one

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It is called Small to Large technique.

Problem.

→ Ответить