Подсказки к задачам

A. Листья

Добавьте в простую реализацию двоичного дерева поиска, рассмотренную на занятии, рекурсивную функцию обхода. Она может работать следующим образом:

• если текущий узел — нулевой, ничего не делать (база рекурсии);
• рекурсивно запуститься от левого поддерева;
• если у текущего узла нет потомков, вывести его value;
• рекурсивно запуститься от правого поддерева.

Данная функция, запущенная от корня дерева, будет выводить ответ на задачу.

B. Листья: валидатор

Используйте set и его методы find() или count(), чтобы проверять, встречалось ли число раньше. Не забывайте добавлять все числа в set.

C. Макс и ожидание маршрутки

Используйте map, где ключ — номер маршрутки, а значение — время её последнего появления. Если маршрутка уже появлялась, вычислите время, прошедшее с её последнего появления; ответ является максимумом из всех таких времён.

D. Макс и супермаркет

Используйте сет пар (время, когда касса освободится; номер кассы). Постоянно извлекайте из этого сета минимум, обновляйте его и заносите обратно в сет.

Вместо сета можно использовать очередь с приоритетами.

E. Макс и командировочные документы

Вам нужно знать:

• сколько существует видов документов;
• сколько существует студентов;
• сколько имеется различных документов.

Всё это можно определить при помощи set<string> и set< pair<string, string> >.

F. Лучше, чем приоритетная очередь

multiset, insert(), erase(), find(), begin(), end().

G. Макс и новогодние подарки

Чтобы решить задачу, нужно уметь обрабатывать каждый шаг Макса быстрее, чем за O(N).

Предположим, что имеется массив A[] из N ячеек (на самом деле создать его, конечно, невозможно), i-я ячейка которого содержит количество конфет, которое нужно добавить во все коробки от i-й до самой последней.

Пусть Макс добавил по K конфет в коробки от L до R. Сделаем A[L] += K и A[R + 1] -= K. После того, как мы сделаем подобные действия для всех шагов, реальное количество конфет в i-й коробке равно сумме всех A[j], где j = 0..i.

Осталось понять, что вместо массива на 10⁹ ячеек можно использовать map. Нужно пройти по нему слева направо (при помощи итераторов), поддерживая текущее количество конфет.

H. Евгений и Пикабу

Это очень сложная задача (что, впрочем, не мешает большому количеству людей уметь её решать).

На прямой последовательно добавляются отрезки. Если новый отрезок пересекается с уже имеющимися, они объединяются. Ответом на каждый запрос является текущее количество непересекающихся отрезков.

Нужно поддерживать сет непересекающихся отрезков (целесообразно для отрезков создать отдельную структуру). При добавлении нового отрезка нужно найти все отрезки, с которыми он пересекается, удалить их из сета и объединить с новым. Для быстрого поиска отрезков следует использовать lower_bound, а далее двумя циклами while найти левую и правую границу пересекающихся отрезков.