Пытался решить задачу декартовым деревом и столкнулся с проблемой, после моего split изменялся root->size но хотя оно не должно. Можете пожалуйста пожалуйста помочь и указать на ошибку. Ссылка на мой код: https://ideone.com/6kVdIO. Задача 191E
UPD Решил просто исправить merge после split но теперь стал ловить тл. Как можно оптимайзить? Можете посоветовать хороший источник Декартки с++
Автокомментарий: текст был обновлен пользователем AI_Avenger (предыдущая версия, новая версия, сравнить).
Пиши хороший рандом, или делай вот так:
(rand()<<15) + rand();
UPD: обычный рандом генерирует числа до +-2^15 т.е. в промежутке от -32к до 32к
Мы с ребятами недавно выяснили, что поведения рандома зависит от операционной системы, в которой вы запускаете программу. Если вы попробуете запустить код выше в запуске Codeforces, то получите число 41 независимо от компилятора (под вижуалкой он не скомпилируется, но если его немного изменить, то там тоже будет 41).
А вот в запуске на ideone все интереснее — там получается число $$$1804289383$$$, как и на моем линуксе. Поскольку этапы ICPC в основном тестируются под линуксом, то на этот недостаток рандома можно забить.
Если вы не уверены, как ведет себя рандом в вашей тестирующей системе, то идейно более правильно использовать
((rand() << 15) ^ rand())
— так все биты в числе действительно получаются случайными, независимо от ОС. В случае со сложением это не работает из-за переноса $$$1$$$ через разряд.После
split
должно изменятьсяroot->size
. Не осталось старой версии корня, есть только два новых дерева.Нужно
merge
их обратно вroot
послеsplit
в строках 112-115. Либо делать дерево персистентным — вместо каждого изменения вершины создавать изменённую копию — но такое дерево требует больше памяти.