hw9

Деревья поиска - 2

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

Ограничение по времени на тест: 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

Решение

B. Неявный ключ

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

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

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

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

Научитесь быстро делать две операции с массивом:

• add i x — добавить после i-го элемента x (0 ≤ i ≤ n)

• del i — удалить i-й элемент (1 ≤ i ≤ n)

Входные данные

На первой строке n0 и m (1 ≤ n0, m ≤ 10^5) — длина исходного массива и количество запросов. На второй строке n0 целых чисел от 0 до 10^9 - 1 — исходный массив. Далее m строк, содержащие запросы. Гарантируется, что запросы корректны: например, если просят удалить i-й элемент, он точно есть.

Выходные данные

Выведите конечное состояние массива. На первой строке количество элементов, на второй строке сам массив.

Пример

Входные данные

3 4
1 2 3
del 3
add 0 9
add 3 8
del 2

Выходные данные

3
9 2 8

Решение

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

Ограничение по времени на тест: 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

Решение

D. Развороты

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

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

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

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

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

Входные данные

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

Выходные данные

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

Пример

Входные данные

5 3
2 4
3 5
2 2

Выходные данные

1 4 5 2 3

Решение