Здравствуйте! Помогите решить задачу. Я написал решение с деревом отрезков и получил TL. Помогите оптимизировать решение. Также прошу у знающих совета/ответа на пару моих вопросов:
1) объясните как лучше всего писать такие деревья отрезков(на массивах или указателях).
2) что быстрее map или unordered_map; Однажды я слышал, что если использовать функцию rehash(N) (N — максимальное кол-во ключей), то unordered_map будет работать очень быстро. Можете подтвердить это или опровергнуть?
Спасибо за внимание!
А зачем MAXN=10^6? Там же 10^5 хватает или я туплю
А неь т, туплю. Там qlogn памяти
Да, вы правы. Изначально я поставил столько же, но получал вердикт access violation.
Дело в том, что ДО, в зависимости от реализации ест 2N памяти или 4N памяти
А можете показать/рассказать как писать неявное ДО с приемлемым потреблением памяти?
Я обычно пишу на указателях, тогда он съесть памяти ровно столько, сколько нужно. Логика такая: если надо писать в вершину, которой нет, создадим её. Если надо читать из вершины, где ничего нет, скажем, что в ней то, что лежит в вершине по умолчанию(зависит от функции на которой дерево строится). Это жрет не более чем qlogn, где q — число запросов изменения. На практике — поменьше, потому что мы не каждый раз создаём logn вершин
Из моей практики: указатели обычно работают дольше, кроме того значительную часть памяти куча забирает под свои нужды. Исходя из этого всесторонне выгоднее выделить заранее массивы:
После этого когда нам нужно выделить очередную вершину, мы просто присваиваем ей номер
sz++подобно тому, как это происходит в боре.Моя реализация на примере задачи подсчёта различных чисел на подотрезке: #ui7bmV. В данном случае дерево также персистентное, но чтобы избавиться от этого, достаточно заменить функцию
copy()наТам, кстати, долго делать сжатое ДО, потому что там логарифм миллиарда. Я бы так делал: построим ДО из 100000 нулей и будем хранить указатель на правую границу(изначально 1) и для каждого числа — список позиций, на которых это число встречается.
Пусть надо добавить число x. Возьмём и запишем его в ДО на указатель правой границы, кинем в список для числа x эту границу и увеличим её на 1
2) Пусть надо удалить число x. Давайте найдём любую его позицию в дереве(из списка) и выкинем эту позицию из списка, а в дереве на соответствующей позиции подставим 0(нейтральный элемент GCD)
Сдал Вашу задачу. Исправления: 1) написал свою ф-цию gcd(a, b); 2) сменил компилятор (заслал под Visual C++ 2010). Решение submit id = 6335684
То есть лучше всегда самому gcd писать? Спасибо!
Стандартное __gcd работает медленней, так что да, лучше писать свое.
My solution accept. I used деревом отрезков and binary search I unused map. Before save numbers and inds. They numbers sorted in non-decreasing order. Number delete ("-") used binary search this number found ind. This in ind number change 0.