Напишите программу, которая будет реализовывать действия в бинарном дереве поиска «вставить», «удалить» и «найти» (по значению). Программа должна обрабатывать запросы четырёх видов:
ADD n — если указанного числа еще нет в дереве, вставлять его и выводить слово «DONE», если уже есть — оставлять дерево как было и выводить слово «ALREADY».
DELETE n — если указанное число есть в дереве, удалять его и выводить слово «DONE», если нет — оставлять дерево как было и выводить слово «CANNOT». При удалении элемента, имеющего два сына, обязательно обменивать значение с максимальным элементом левого поддерева.
SEARCH — следует выводить слово «YES» (если значение найдено в дереве) или слово «NO» (если не найдено). Дерево при этом не меняется.
PRINTTREE — выводить все дерево, обязательно используя алгоритм, указанный в формате вывода результатов.
В каждой строке входных данных записан один из запросов ADD n или DELETE n или SEARCH n или PRINTTREE. Гарантируется, что запросы PRINTTREE будут вызываться только в моменты, когда дерево не пустое. Общее количество запросов не превышает 1000, из них не более 20 запросов PRINTTREE.
Для каждого запроса выводите ответ на него. Для запросов ADD, DELETE и SEARCH — соответствующее слово в отдельной строке. На запрос PRINTTREE надо выводить дерево, обязательно согласно такому алгоритму:
template<class T> void print_tree(Node<T> *p, int level)
{
if(p==NULL)
return;
print_tree(p->left, level+1);
for(int i=0; i<level; i++)
cout << ".";
cout << p->data << endl;
print_tree(p->right, level+1);
}
(Изначальный вызов этой функции — print_tree(root,0).)
ADD 2 ADD 7 ADD 5 PRINTTREE ADD 5 DELETE 3 ADD 0 PRINTTREE DELETE 7 PRINTTREE
DONE DONE DONE 2 ..5 .7 ALREADY CANNOT DONE .0 2 ..5 .7 DONE .0 2 .5
Знаете ли вы, почему четвертый этаж заперт и там не останавливается лифт? Потому что на самом деле четвертый, запертый, этаж, где не останавливается лифт, содержит бесконечное количество комнат, пронумерованных натуральными числами. На этот этаж регулярно приезжают дети, каждый из которых заранее выбрал, в какую комнату он хочет заселиться. Если выбранная комната оказывается свободна, то ребенок занимает ее, в противном случае он занимает первую свободную комнату с бóльшим номером.
Кроме того, некоторые дети уезжают в середине смены. Сразу после отъезда ребенка его комната становится доступна для заселения следующего.
Промоделируйте работу преподавателей, ответственных за четвертый этаж и научитесь быстро сообщать приезжающим детям, какую комнату им следует занимать.
Первая строка входного файла содержит натуральное число \(n\) — количество прибытий и отъездов, происходящих в течение смены (\(1 \le n \le 100\,000\)).
Следующие \(n\) строк содержат информацию об ЛКШатах. Число \(a > 0\) обозначает, что приехал школьник, желающий занять комнату номер \(a\) (\(1 \le a \le 100\,000\)). Число \(a < 0\) обозначает, что из комнаты номер \(|a|\) уехал школьник (гарантируется, что эта комната не была пуста).
Для каждого приезжающего школьника выведите одно натуральное число — номер комнаты, в которую он поселится.
6 5 5 5 -6 5 5
5 6 7 6 8
Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков.
Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.
Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна.
Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная.
В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 106).
На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.
1 1 1
1 1
2 1 1 1000000
2 1 2
8 3 1 2 3 4 1 6 7 8
2 2 6
Цифровой поезд нового поколения состоит из вагонов, содержащих по \(N\) мест для пассажиров. Все места расположены вдоль вагона и пронумерованы от \(1\) до \(N\). Вход в вагон расположен левее места \(1\), а места \(1, 2, \ldots, N\) расположены правее от входа в соответствующем порядке. \(N\) пассажиров готовятся сесть в поезд. Каждый заходящий в вагон характеризуется номером места \(A_i\) и своей массой \(B_i\). Когда пассажир идет по вагону от входа до своего места, некоторые пассажиры, которые сели ранее, мешают ему пройти. Пассажир испытывает неудобство, каждый раз проходя мимо человека массы большей, чем у него самого. Суммарным неудобством пассажира при посадке называется количество раз, когда он испытывал неудобство при движении к своему месту от входа в вагон. Ваша задача — по заданному порядку посадки пассажиров найти суммарное неудобство каждого.
Входной файл состоит из одного или нескольких наборов входных данных. Каждый набор начинается с целого числа \(N\; (1 \leq N \leq 100\,000)\) — количества мест (пассажиров). Далее набор входных данных содержит пары целых чисел \(A_i, B_i\; (1 \leq A_i \leq N, 1 \leq B_i \leq 10^9)\). Все числа \(A_i\) и \(B_i\) различны между собой. То есть номера мест пассажиров образуют перестановку. Пассажиры садятся в поезд именно в том порядке, в котором они заданы во входном файле. Количество наборов входных данных не превосходит \(5\).
Выведите ответ на каждый набор входных данных. Каждый ответ должен состоять из последовательности \(N\) целых чисел \(P_1, P_2, \ldots, P_N\), где \(P_i\) — суммарное неудобство \(i\)-го пассажира.
3 1 2 2 3 3 1 2 1 1 2 2
0 0 2 0 0