Реализуйте просто двоичное дерево поиска.
Входной файл содержит описание операций с деревом, их количество не превышает 100. В каждой строке находится одна из следующих операций:
-
insert
$x$ — добавить в дерево ключ$x$ . Если ключ$x$ есть в дереве, то ничего делать не надо; -
delete
$x$ — удалить из дерева ключ$x$ . Если ключа$x$ в дереве нет, то ничего делать не надо; -
exists
$x$ — если ключ$x$ есть в дереве выведите «true
», если нет «false
»; -
next
$x$ — выведите минимальный элемент в дереве, строго больший$x$ , или «none
» если такого нет; -
prev
$x$ — выведите максимальный элемент в дереве, строго меньший$x$ , или «none
» если такого нет.
В дерево помещаются и извлекаются только целые числа, не превышающие по модулю
Выведите последовательно результат выполнения всех операций exists
, next
, prev
. Следуйте формату выходного файла из примера.
Входные данные
insert 2
insert 5
insert 3
exists 2
exists 4
next 4
prev 4
delete 5
next 4
prev 4
Выходные данные
true
false
5
3
none
3
Реализуйте сбалансированное двоичное дерево поиска.
Входной файл содержит описание операций с деревом, их количество не превышает
-
insert
$x$ — добавить в дерево ключ$x$ . Если ключ$x$ есть в дереве, то ничего делать не надо; -
delete
$x$ — удалить из дерева ключ$x$ . Если ключа$x$ в дереве нет, то ничего делать не надо; -
exists
$x$ — если ключ$x$ есть в дереве выведите «true
», если нет «false
»; -
next
$x$ — выведите минимальный элемент в дереве, строго больший$x$ , или «none
» если такого нет; -
prev
$x$ — выведите максимальный элемент в дереве, строго меньший$x$ , или «none
» если такого нет.
В дерево помещаются и извлекаются только целые числа, не превышающие по модулю
Выведите последовательно результат выполнения всех операций exists
, next
, prev
. Следуйте формату выходного файла из примера.
Входные данные
insert 2
insert 5
insert 3
exists 2
exists 4
next 4
prev 4
delete 5
next 4
prev 4
Выходные данные
true
false
5
3
none
3
Вы работаете в компании Макрохард и вас попросили реализовать структуру данных, которая будет хранить множество целых ключей.
Будем считать, что ключи хранятся в бесконечном массиве
Insert
Операция должна выполняться следующим образом:
- Если ячейка
$A[L]$ пуста, присвоить$A[L] \gets K$ . - Если
$A[L]$ непуста, выполнитьInsert
$(L+1, A[L])$ и затем присвоить$A[L] \gets K$ .
По заданным
Insert
Insert
Insert
Первая строка входного файла содержит числа Insert
, которое следует выполнить и Insert
Следующая строка содержит Insert
, которые следует выполнить
Выведите содержимое массива после выполнения всех сделанных операций Insert
. На первой строке выведите
Входные данные
5 4
3 3 4 1 3
Выходные данные
6
4 0 5 2 3 1
Реализуйте структуру данных, которая поддерживает множество
-
$\operatorname{add}(i)$ — добавить в множество$S$ число$i$ (если он там уже есть, то множество не меняется); -
$\operatorname{sum}(l, r)$ — вывести сумму всех элементов$x$ из$S$ , которые удовлетворяют неравенству$l ⩽ x ⩽ r$ .
Исходно множество
Если операция «+
Во всех запросах и операциях добавления параметры лежат в интервале от
Для каждого запроса выведите одно число — ответ на запрос.
Входные данные
6
+ 1
+ 3
+ 3
? 2 4
+ 1
? 2 4
Выходные данные
3
7
Напишите программу, реализующую структуру данных, позволяющую добавлять и удалять элементы, а также находить
Первая строка входного файла содержит натуральное число
- 1: Добавить элемент с ключом
$k_i$ . - 0: Найти и вывести
$k_i$ -й максимум. - -1: Удалить элемент с ключом
$k_i$ .
Гарантируется, что в процессе работы в структуре не требуется хранить элементы с равными ключами или удалять несуществующие элементы. Также гарантируется, что при запросе
Для каждой команды нулевого типа в выходной файл должна быть выведена строка, содержащая единственное число —
Входные данные
11
1 5
1 3
1 7
0 1
0 2
0 3
-1 5
1 10
0 1
0 2
0 3
Выходные данные
7
5
3
10
7
3
Научитесь быстро делать две операции с массивом:
-
add i x
— добавить после$i$ -го элемента$x$ $(0 ⩽ i ⩽ n)$ -
del i
— удалить$i$ -й элемент$(1 ⩽ i ⩽ n)$
На первой строке
Выведите конечное состояние массива. На первой строке количество элементов, на второй строке сам массив.
Входные данные
3 4
1 2 3
del 3
add 0 9
add 3 8
del 2
Выходные данные
3
9 2 8
Вам дан массив
Выведите порядок элементов в массиве после выполнения всех операций.
В первой строке входного файла указаны числа
Выведите
Входные данные
6 3
2 4
3 5
2 2
Выходные данные
1 4 5 2 3 6
Вам дан массив
Выведите порядок элементов в массиве после выполнения всех операций.
В первой строке входного файла указаны числа
Выведите
Входные данные
5 3
2 4
3 5
2 2
Выходные данные
1 4 5 2 3
В многострадальном Тридесятом государстве опять готовится дорожная реформа. Впрочем, надо признать, дороги в этом государстве находятся в довольно плачевном состоянии. Так что реформа не повредит. Одна проблема — дорожникам не развернуться, поскольку в стране действует жесткий закон — из каждого города должно вести не более двух дорог. Все дороги в государстве двусторонние, то есть по ним разрешено движение в обоих направлениях (разумеется, разметка отсутствует). В результате реформы некоторые дороги будут строиться, а некоторые другие закрываться на бессрочный ремонт.
Петя работает диспетчером в службе грузоперевозок на дальние расстояния. В связи с предстоящими реформами, ему необходимо оперативно определять оптимальные маршруты между городами в условиях постоянно меняющейся дорожной ситуации. В силу большого количества пробок и сотрудников дорожной полиции в городах, критерием оптимальности маршрута считается количество промежуточных городов, которые необходимо проехать.
Помогите Пете по заданной последовательности сообщений об изменении структуры дорог и запросам об оптимальном способе проезда из одного города в другой, оперативно отвечать на запросы.
В первой строке входного файла заданы числа
Гарантируется, что в начале и после каждого изменения никакие два города не соединены более чем одной дорогой, и из каждого города выходит не более двух дорог. Никакой город не соединяется дорогой сам с собой.
На каждый запрос вида «?
Входные данные
5 4 6
1 2
2 3
1 3
4 5
? 1 2
? 1 5
- 2 3
? 2 3
+ 2 4
? 1 5
Выходные данные
0
-1
1
2