Size: a a a

2021 April 21

K

Kotomord_λapki in pro.algorithms
самая тяжёлая функция вот эта

   void revert(int from, int to) {
       CartesianTreePair o1 = split(ones, from-1);
       CartesianTreePair o2 = split(o1.right, to);

       CartesianTreePair z1 = split(zeroes, from-1);
       CartesianTreePair z2 = split(z1.right, to);

       ones = union(o1.left, union(z2.left, o2.right));
       zeroes = union(z1.left, union(o2.left, z2.right));
   }
источник

K

Kotomord_λapki in pro.algorithms
сплит не удаляющий, значение переходит в левое дерево
источник

K

Kotomord_λapki in pro.algorithms
если есть
источник

CD

Constantine Drozdov in pro.algorithms
а, я всё понял, день долбоебова
источник

CD

Constantine Drozdov in pro.algorithms
у него был правый потомок (с вероятностью 1/2)
источник

CD

Constantine Drozdov in pro.algorithms
источник

K

Kotomord_λapki in pro.algorithms
но гарантированно можно выбрать рандомное поддерево глубины корень от размера, кстати
источник

NK

Nikolai Karpov in pro.algorithms
Чего
источник

NK

Nikolai Karpov in pro.algorithms
От размера чего?
источник

K

Kotomord_λapki in pro.algorithms
от размера дерева
источник

K

Kotomord_λapki in pro.algorithms
то есть у нас есть декартово дерево со случайными приоритетами,  мы выбираем подмножество вершин и сводим его в ДД с этими же приоритетами
источник

K

Kotomord_λapki in pro.algorithms
утверждается, что если в дереве N вершин, то в подмножестве может быть глубина  sqrt(N)
источник

K

Kotomord_λapki in pro.algorithms
источник

NK

Nikolai Karpov in pro.algorithms
А ну это понятно
источник

NK

Nikolai Karpov in pro.algorithms
В любом массиве есть возрастающая последовательность или убывающая длины корень
источник

K

Kotomord_λapki in pro.algorithms
ну вот, порядок - по ключам, значения - приоритеты, находим последовательность и по ней строим дерево
источник

K

Kotomord_λapki in pro.algorithms
но я не верю, что там есть тест под мой сид
источник

NK

Nikolai Karpov in pro.algorithms
Надо всего-то перебрать 2^64 сидов и под каждый построить тест :)
источник

K

Kotomord_λapki in pro.algorithms
в тесте, на котором TL, высота обоих деревьев никогда не превышает 60
источник

NK

Nikolai Karpov in pro.algorithms
Можно же одним декартовым справится
источник