необходимо придумать структуру данных типа std::set(history)+std::set+std::stack т.е. со свойствами
1) инициализировать объект (= в нем ничего нет и ничего не было до этого)
2) добавлять элемент в случае, если в объекте такового нет и не было до (т.е. добавляется предварительный поиск)
3) помечать элемент как удаленный
4) возможность завершить работу с объектом, если все его элементы помченны на удаление.

Шаг 1 выполняется n раз,
Шаги 2-4: n*m, n>>1, m>>1

Какая оптимальная структура данных подойдет для задачи?