алгоритмы и структуры. деревья

1. Задача A. RMQ
Имя входного файла: rmq.in
Имя выходного файла: rmq.out
Формат входного файла:
В первой строке находится число n — размер массива. (1 ≤ n ≤ 500000) Во второй строке
находится n чисел a i — элементы массива. Далее содержится описание операций, их количество не
превышает 1000000. В каждой строке находится одна из следующих операций:
• set i x — установить a[i] в x.
• min i j — вывести значение минимального элемента в массиве на отрезке с i по j, гарантируется,
что (1 ≤ i ≤ j ≤ n).
В массив помещаются только целые числа, не превышающие по модулю 10^9 .
Формат выходного файла:
Выведите последовательно результат выполнения всех операций min.
выходного файла из примера.

2. Задача B. RSQ
Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Формат входного файла
В первой строке находится число n — размер массива. (1 ≤ n ≤ 500000) Во второй строке
находится n чисел a[i] — элементы массива. Далее содержится описание операций, их количество не
превышает 1000000. В каждой строке находится одна из следующих операций:
• set i x — установить a[i] в x.
• sum i j — вывести значение суммы элементов в массиве на отрезке с i по j, гарантируется, что
(1 ≤ i ≤ j ≤ n).
Все числа во входном файле и результаты выполнения всех операций не превышают по модулю 10^18
Формат выходного файла
Выведите последовательно результат выполнения всех операций sum.

3. Задача C. Двоичное дерево поиска
Имя входного файла: bst.in
Имя выходного файла: bst.out
Формат входного файла
Входной файл содержит описание операций с деревом, их количество не превышает 100000. В
каждой строке находится одна из следующих операций:
• insert x — добавить в дерево ключ x. Если ключ x есть в дереве, то ничего делать не надо
• delete x — удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не надо
• exists x — если ключ x есть в дереве выведите «true», если нет «false»
• next x — выведите минимальный элемент в дереве, строго больший x, или «none» если такого нет
• prev x — выведите максимальный элемент в дереве, строго меньший x, или «none» если такого нет
В дерево помещаются и извлекаются только целые числа, не превышающие по модулю 1e9 .
Формат выходного файла
Выведите последовательно результат выполнения всех операций exists, next, prev. Следуйте
формату выходного файла из примера

4. Задача H. Прямоугольники
Имя входного файла: pail.in
Имя выходного файла: pail.out
Есть таблица T размера N × M . Элементами таблицы являются прямоугольники T_ij, где
0 ≤ i < N и 0 ≤ j < M. Прямоугольник T_ij задаётся четвёркой чисел (x1_ij, y1_ij, x2_ij, y2_ij),
где (x1_ij, y1_ij) и (x2_ij, y2_ij)  — координаты противоположных углов прямоугльника.
Стороны прямоугольника параллельны осям координат.
Далее вам поступают запросы. Каждый запрос состоит из четырёх чисел: (r1, c1, r2, c2 ). Ответом
на такой запрос является площадь фигуры, являющейся пересечением всех прямоугольников T_ij
таких, что min(r1, r2) ≤ i ≤ max(r1, r2 ) и min(c1, c2) ≤ j ≤ max(c1, c2). Запросов очень много,
поэтому мы просим вас вывести сумму ответов на все запросы по модулю 10^9 + 7.
Формат входного файла:
В первой строке записаны два целых числа N и M — размеры таблицы T (1 ≤ N, M ≤ 127).
Далее в N строках описывается таблица T : в (i + 1)-й строке (j + 1)-я четвёрка чисел x1_ij, y1_ij, x2_ij, y2_ij
описывает прямоугольник T_ij . Гаранируется, что |xk_ij|, |yk_ij| ≤ 10^6
Дальше в отдельной строке записано четыре числа. Первое из них, число Q — количество
запросов (1 ≤ Q ≤ 5·10^6 ). Следующие три числа — это A, B, v0 (0 ≤ A, B, v 0 < 10^9 +7). При помощи
этих чисел генерируется бесконечная последовательность {v[i]} по правилу v[i] = (A*v[i−1] + B) mod (10^9 + 7).
После этого k-й запрос (запросы нумеруются с единицы) задаётся следующей четвёркой чисел:
(v[4k−3] mod N, v[4k−2] mod M, v[4k−1] mod N, v[4k] mod M).
Формат выходного файла
Выведите сумму ответов на все запросы по модулю 10^9 + 7.

5. Задача I. Конфетки
Имя входного файла: candies.in
Имя выходного файла: candies.out
У Кролика день рождения! Он пригласил в гости n гостей. Чтобы гостям не было грустно
и скучно, Кролик купил n коробок конфет. Кролик любит разнообразие, поэтому конфеты были
разные. В i-й коробке лежало a[i] конфет.
В назначенный день с самого утра к Кролику начали приходить гости. Каждый гость
характеризуется своей наглостью b[i] . Это означает, что, зайдя домой к Кролику и увидев коробки
конфет, он брал из каждой коробки, в которой не меньше, чем b[i], конфет, по одной и съедал её.
Например, у Винни-Пуха вполне могла была быть наглость один. Это значит, что он бы съел по
конфете из каждой коробки.
Вечером, когда гости разошлись, Кролику стало интересно, кто съел сколько конфет. Помогите
ему определить это.
Формат входного файла
В первой строке задано целое число n (1 ≤ n ≤ 100 000) — количество коробок конфет. В
следующей строке задано n натуральных чисел a[i] (1 ≤ a[i] ≤ 10^9 ) — сколько конфет в каждой
коробке.
Далее, в следующей строке задано число число m (1 ≤ m ≤ 100 000) — количество гостей. В
четвёртой и последней строке задано m чисел b[i] (1 ≤ b[i] ≤ 10^9 ) — наглости гостей.
Формат выходного файла
В выходной файл выведите n строк, i-ая из которых должна содержать количество конфет
съеденных i-ым гостем.