Search tree

Дерево поиска

A. Простое двоичное дерево поиска

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 512 мегабайт

Реализуйте просто двоичное дерево поиска.

Формат входных данных

Входной файл содержит описание операций с деревом, их количество не превышает 100. В каж- дой строке находится одна из следующих операций:

• insert x — добавить в дерево ключ x. Если ключxесть в дереве, то ничего делать не надо

• delete x — удалить из дерева ключ x. Если ключаxв дереве нет, то ничего делать не надо

• exists x — если ключ x есть в дереве выведите «true», если нет «false»

• next x — выведите минимальный элемент в дереве, строго больший x, или «none» если такого нет

• prev x — выведите максимальный элемент в дереве, строго меньший x, или «none» если такого нет

В дерево помещаются и извлекаются только целые числа, не превышающие по модулю 10^9.

Формат выходных данных

Выведите последовательно результат выполнения всех операций 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

Решение

B. Сбалансированное двоичное дерево поиска

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 512 мегабайт

Реализуйте сбалансированное двоичное дерево поиска.

Формат входных данных

Входной файл содержит описание операций с деревом, их количество не превышает 10^5. В каж- дой строке находится одна из следующих операций:

• insert x — добавить в дерево ключ x. Если ключxесть в дереве, то ничего делать не надо

• delete x — удалить из дерева ключ x. Если ключаxв дереве нет, то ничего делать не надо

• exists x — если ключ x есть в дереве выведите «true», если нет «false»

• next x — выведите минимальный элемент в дереве, строго больший x, или «none» если такого нет

• prev x — выведите максимальный элемент в дереве, строго меньший x, или «none» если такого нет

В дерево помещаются и извлекаются только целые числа, не превышающие по модулю 10^9.

Формат выходных данных

Выведите последовательно результат выполнения всех операций 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

C. Декартово дерево

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Вам даны пары чисел (ai, bi). Необходимо построить декартово дерево, такое что i-я вершина имеет ключи (ai, bi), вершины с ключом ai образуют бинарное дерево поиска, а вершины с ключом bi образуют кучу.

Формат входных данных

В первой строке записано число N — количество пар. Далее следует N ( 1 ⩽ N ⩽ 300 000) пар (ai, bi). Для всех пар |ai|; |bi| ⩽ 30 000. ai̸=aj и bi̸=bj для всех i̸=j .

Формат выходных данных

Если декартово дерево с таким набором ключей построить возможно, выведите в первой стро- ке «YES», в противном случае выведите «NO». В случае ответа «YES» выведите N строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номера предка, номера левого сына и номера правого сына. Если у вершины отсутствует предок или какой либо из сыновей, выведите на его месте число 0. Если подходящих деревьев несколько, выведите любое.

Пример

стандартный ввод

7
5 4
2 2
3 9
0 5
1 3
6 6
4 11

стандартный вывод

YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0

Решение

D. Добавление ключей

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Вы работаете в компании Макрохард и вас попросили реализовать структуру данных, которая будет хранить множество целых ключей. Будем считать, что ключи хранятся в бесконечном массиве A, проиндексированном с 1 , исходно все его ячейки пусты. Структура данных должна поддерживать следующую операцию: Insert(L,K), где L — позиция в массиве, а K — некоторое положительное целое число. Операция должна выполняться следующим образом:

• Если ячейка A[L] пуста, присвоить A[L] <- K.

• Если A[L] непуста, выполнить Insert(L+ 1,A[L]) и затем присвоить A[L] <- K.

По заданным N целым числам L1, L2,...,LN выведите массив после выполнения последователь ности операций: Insert(L1 , 1 ) Insert(L2 , 2 ) ... Insert(LN,N)

Формат входных данных

Первая строка входного файла содержит числа N — количество операций Insert, которое следует выполнить и M — максимальную позицию, которая используется в операциях Insert ( 1 ⩽ N ⩽ 131 072, 1 ⩽ M ⩽ 131 072). Следующая строка содержит N целых чисел Li, которые описывают операции Insert, которые следует выполнить ( 1 ⩽ Li ⩽ M).

Формат выходных данных

Выведите содержимое массива после выполнения всех сделанных операций Insert. На первой строке выведите W — номер максимальной непустой ячейки в массиве. Затем выведите W целых чисел — A[1], A[2],..., A[W]. Выводите нули для пустых ячеек.

Пример

стандартный ввод

5 4
3 3 4 1 3

стандартный вывод

6
4 0 5 2 3 1

Решение

E. И снова сумма

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 3 секунды

Ограничение по памяти: 256 мегабайт

Реализуйте структуру данных, которая поддерживает множество S целых чисел, с котором раз- решается производить следующие операции:

• add(i)— добавить в множество S число i (если он там уже есть, то множество не меняется);

• sum(l, r) — вывести сумму всех элементов x из S, которые удовлетворяют неравенству l ⩽ x ⩽ r.

Формат входных данных

Исходно множество S пусто. Первая строка входного файла содержит n — количество операций ( 1 ⩽ n ⩽ 300 000).Следующие n строк содержат операции. Каждая операция имеет вид либо «+i», либо «? l r». Операция «? l r» задает запрос sum(l, r). Если операция « +i » идет во входном файле в начале или после другой операции «+», то она задает операцию add(i). Если же она идет после запроса «?», и результат этого запроса былy, то выполняется операция add((i + y) mod 10^9 ). Во всех запросах и операциях добавления параметры лежат в интервале от 0 до 10^9.

Формат выходных данных

Для каждого запроса выведите одно число — ответ на запрос.

Пример

стандартный ввод

6
+ 1
+ 3
+ 3
? 2 4
+ 1
? 2 4

стандартный вывод

3
7

Решение

F. K-й максимум

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 512 мегабайт

Напишите программу, реализующую структуру данных, позволяющую добавлять и удалять эле- менты, а также находить k-й максимум.

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество команд (n ⩽ 100 000). Последующиеnстрок содержат по одной команде каждая. Команда записывается в виде двух чиселc i и ki — тип и аргумент команды соответственно (|ki| ⩽ 10^9 ). Поддерживаемые команды:

• +1 (или просто 1 ): Добавить элемент с ключом ki.

• 0 : Найти и вывести ki-й максимум.

• -1 : Удалить элемент с ключом ki.

Гарантируется, что в процессе работы в структуре не требуется хранить элементы с равными ключами или удалять несуществующие элементы. Также гарантируется, что при запросе ki-го мак- симума, он существует.

Формат выходных данных

Для каждой команды нулевого типа в выходной файл должна быть выведена строка, содержа- щая единственное число — ki-й максимум.

Пример

стандартный ввод

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

Решение

G. Переместить в начало

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 6 секунд

Ограничение по памяти: 512 мегабайт

Вам дан массив a1 = 1; a2 = 2,..., an = n и последовальность операций: переместить элементы с li по ri в начало массива. Например, для массива 2, 3, 6, 1, 5, 4 , после операции (2,4) новый по- рядок будет 3, 6, 1, 2, 5, 4. А после применения операции (3,4) порядок элементов в массиве будет 1, 2, 3, 6, 5, 4. Выведите порядок элементов в массиве после выполнения всех операций.

Формат входных данных

В первой строке входного файла указаны числа n и m ( 2 ⩽ n ⩽100 000, 1 ⩽ m ⩽100 000) — число элементов в массиве и число операций. Следующие m строк содержат операции в виде двух целых чисел: li и ri ( 1 ⩽ li ⩽ ri ⩽ n ).

Формат выходных данных

Выведите n целых чисел — порядок элементов в массиве после применения всех операций.

Пример

стандартный ввод

6 3
2 4
3 5
2 2

стандартный вывод

1 4 5 2 3 6

Решение

H. Различные буквы

Имя входного файла: log.in

Имя выходного файла: log.out

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

Вы работаете со списком из строчных латинских букв. Изначально список пуст. Вы должны поддерживать следующие операции:

• insert ⟨index⟩ ⟨number⟩ ⟨letter⟩ — добавить ⟨number⟩ букв ⟨letter⟩ перед буквой с индексом ⟨index⟩.

• remove ⟨index⟩ ⟨number⟩ — удалить ⟨number⟩ букв, начиная с индекса ⟨index⟩.

• query ⟨index 1 ⟩ ⟨index 2 ⟩ — вывести количество различных букв на отрезке с ⟨index 1 ⟩ до ⟨index 2 ⟩включительно.

Буквы нумеруются с 1.

Формат входных данных

В первой строке входного файла содержится единственное целое число n — количество операций ( 1 ⩽ n ⩽ 30 000). Следующие по n строк содержат описание операций. Описание операции начинается с типа операции: '+' для добавления, '-' для удаления и '?' для запроса. Дальше следует аргументы запроса, описанные в условиях выше. Все запросы корректны, элементы с такими индексами существуют, нет запросов на удаление несуществующих элементов. ⟨number⟩ добавления, удаления не превышает 10 000.

Формат выходных данных

Для каждого запроса query выведите одно целое число — количество различных букв на отрезке ⟨index 1 ⟩, ⟨index 2 ⟩ включительно.

Пример

log.in

8
+ 1 4 w
+ 3 3 o
? 2 3
- 2 2
? 2 3
+ 2 2 t
? 1 6
- 1 6

log.out

2
1
3

Замечание

Пояснение к примеру:

1. wwww
2. wwoooww
3. w[wo]ooww: 2 различные буквы
4. wooww
5. w[oo]ww: 1 буква
6. wttooww
7. [wttoow]w: 3 различные буквы
8. w

I. Эх, дороги

Имя входного файла: roads.in

Имя выходного файла: roads.out

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мегабайт

В многострадальном Тридесятом государстве опять готовится дорожная реформа. Впрочем, на- до признать, дороги в этом государстве находятся в довольно плачевном состоянии. Так что реформа не повредит. Одна проблема — дорожникам не развернуться, поскольку в стране действует жесткий закон — из каждого города должно вести не более двух дорог. Все дороги в государстве двусторон- ние, то есть по ним разрешено движение в обоих направлениях (разумеется, разметка отсутствует). В результате реформы некоторые дороги будут строиться, а некоторые другие закрываться на бес- срочный ремонт. Петя работает диспетчером в службе грузоперевозок на дальние расстояния. В связи с предстоя- щими реформами, ему необходимо оперативно определять оптимальные маршруты между городами в условиях постоянно меняющейся дорожной ситуации. В силу большого количества пробок и со- трудников дорожной полиции в городах, критерием оптимальности маршрута считается количество промежуточных городов, которые необходимо проехать. Помогите Пете по заданной последовательности сообщений об изменении структуры дорог и за- просам об оптимальном способе проезда из одного города в другой, оперативно отвечать на запросы.

Формат входных данных

В первой строке входного файла заданы числа n — количество городов, m — количество дорог в начале реформы и q — количество сообщений об изменении дорожной структуры и запросов ( 1 ⩽ n, m ⩽ 100 000, q ⩽ 200 000). Следующие m строк содержат по два целых числа каждая — пары городов, соединенных дорогами перед реформой. Следующие q строк содержат по три элемента, разделенных пробелами. «+i j » означает строительство дороги от города i до города j, «-i j » означает закрытие дороги от города i до города j, «? i j » означает запрос об оптимальном пути между городами i и j. Гарантируется, что в начале и после каждого изменения никакие два города не соединены более чем одной дорогой, и из каждого города выходит не более двух дорог. Никакой город не соединяется дорогой сам с собой.

Формат выходных данных

На каждый запрос вида «? i j » выведите одно число — минимальное количество промежуточ- ных городов на маршруте из города i в город j. Если проехать из i в j невозможно, выведите -1.

Пример

roads.in

5 4 6
1 2
2 3
1 3
4 5
? 1 2
? 1 5
- 2 3
? 2 3
+ 2 4
? 1 5

roads.out

0
-1
1
2