Segment tree

Дерево отрезков

A. Сумма простая

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

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

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

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

Вам нужно научиться отвечать на запрос «сумма чисел на отрезке». Массив не меняется. Запросов много. Отвечать на каждый запрос следует за O(1).

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

Размер массива — n и числа x, y, a0 , порождающие массив a: ai= (x * a{i-1} + y) mod 2^16 Далее следует количество запросовmи числа z, t, b0, порождающие массив b: bi = (z * {_bi-1} + t) mod 2^30.

Массив c строится следующим образом: ci =bi mod n. Запросы: i-й из них — найти сумму на отрезке от min(c2i; c2{i+1}) до max(c2i; c2{i+1}) в массиве a. Ограничения: 1 ⩽ n ⩽ 10^7 , 0 ⩽ m ⩽ 10^7. Все числа целые от 0 до 2^16. t может быть равно -1.

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

Выведите сумму всех сумм.

Пример

sum0.in

3 1 2 3
3 1 -1 4

sum0.out

23

Замечание

a = { 3, 5, 7}, b = { 4, 3, 2, 1, 0, 2^30 - 1}, c = { 1, 0, 2, 1, 0, 0}, запросы = { [0;1], [1;2], [0;0]}, суммы = { 8, 12, 3}.

Решение

B. RSQ

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

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

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

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

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

В первой строке находится число n — размер массива. ( 1 ⩽ n ⩽ 500,000) Во второй строке находится n чисел ai — элементы массива. Далее содержится описание операций, их количество не превышает 1,000,000. В каждой строке находится одна из следующих операций:

• set i x — установить a[i] в x.

• sum i j — вывести значение суммы элементов в массиве на отрезке сi по j, гарантируется, что ( 1 ⩽ i ⩽ j ⩽ n).

Все числа во входном файле и результаты выполнения всех операций не превышают по модулю 10^18.

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

Выведите последовательно результат выполнения всех операций sum. Следуйте формату выход- ного файла из примера.

Пример

rsq.in

5
1 2 3 4 5
sum 2 5
sum 1 5
sum 1 4
sum 2 4
set 1 10
set 2 3
set 5 2
sum 2 5
sum 1 5
sum 1 4
sum 2 4

rsq.out

14
15
10
9
12
22
20
10

Решение

Задача C. RMQ

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

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

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

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

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

В первой строке находится число n — размер массива. ( 1 ⩽ n ⩽ 10^5 ) Во второй строке находится n чисел ai — элементы массива. Далее содержится описание операций, их количество не превышает 2 * 10^5. В каждой строке находится одна из следующих операций:

• set i j x — установить все a[k], i ⩽ k ⩽ j в x.

• add i j x — увеличить все a[k], i ⩽ k ⩽ j на x.

• min i j — вывести значение минимального элемента в массиве на отрезке сi по j, гарантируется, что ( 1 ⩽ i ⩽ j ⩽ n).

Все числа во входном файле и результаты выполнения всех операций не превышают по модулю 10^18.

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

Выведите последовательно результат выполнения всех операций min. Следуйте формату выход ного файла из примера.

Пример

rmq2.in

5
1 2 3 4 5
min 2 5
min 1 5
min 1 4
min 2 4
set 1 3 10
add 2 4 4
min 2 5
min 1 5
min 1 4
min 2 4

rmq2.out

2
1
1
2
5
5
8
8

Решение

D. Художник

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

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

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

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

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

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

В первой строке входного файла содержится общее количество нарисованных отрезков ( 1 ⩽ n ⩽ 100 000). В последующихnстроках содержится описание операций. Каждая операция описывается строкой вида c x l, где c — цвет отрезка (W для белых отрезков,B для черных), а сам отрезок имеет вид [x; x+l], причем координаты обоих концов — целые числа, не превосходящие по модулю 500 000. Длина задается положительным целым числом.

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

После выполнения каждой из операций необходимо вывести в выходной файл на отдельной строке количество черных отрезков на картине и их суммарную длину, разделенные одним пробелом.

Пример

painter.in

7
W 2 3
B 2 2
B 4 2
B 3 2
B 7 2
W 3 1
W 0 10

painter.out

0 0
1 2
1 4
1 4
2 6
3 5
0 0

Решение

E. Криптография

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

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

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

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

Задано n матриц A1, A2,..., An размера 2 * 2. Необходимо для нескольких запросов вычислить произведение матриц Ai, Ai+1,..., Aj. Все вычисления производятся по модулюr.

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

Первая строка входного файла содержит числа r ( 1 ⩽ r ⩽ 10 000), n ( 1 ⩽ n ⩽ 200 000) и m ( 1 ⩽ m ⩽ 200 000). Следующие n блоков по две строки содержащие по два числа в строке — описания матриц. Затем следуют m пар целых чисел от 1 до n, запросы на произведение на отрезке.

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

Выведите m блоков по две строки, по два числа в каждой — произведения на отрезках. Разде ляйте блоки пустой строкой. Все вычисления производятся по модулю r.

Пример

crypto.in

3 4 4
0 1
0 0
2 1
1 2
0 0
0 2
1 0
0 2
1 4
2 3
1 3
2 2

crypto.out

0 2
0 0
0 2
0 1
0 1
0 0
2 1
1 2

Решение

F. Разреженные таблицы

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

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

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

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

Дан массив изnчисел. Требуется написать программу, которая будет отвечать на запросы сле- дующего вида: найти минимум на отрезке междуuиvвключительно.

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

В первой строке входного файла даны три натуральных числаn, m ( 1 ⩽ n ⩽ 10^5 , 1 ⩽ m ⩽ 10^7 ) и a1 ( 0 ⩽ a1 < 16 714 589) — количество элементов в массиве, количество запросов и первый элемент массива соответственно. Вторая строка содержит два натуральных числа u1 и v1 ( 1 ⩽ u1 ; v1 ⩽ n) — первый запрос. Элементы a2, a3,..., an задаются следующей формулой:

ai+1 = (23 * ai + 21563) mod 16714589.

Например, при n = 10, a1 = 12345 получается следующий массив: a = ( 12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233 , 570265, 13137658, 1325095). Запросы генерируются следующим образом:

ui+1 = ((17 * ui + 751 + ansi + 2i) mod n) + 1,

vi+1 = ((13 * vi + 593 + ansi + 5i) mod n) + 1,

где ansi — ответ на запрос номер i.

Обратите внимание, что ui может быть больше, чем vi.

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

В выходной файл выведите um, vm и ansm (последний запрос и ответ на него).

Примеры

sparse.in

10 8 12345
3 9

sparse.out

5 3 1565158

Решение

G. Окна

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

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

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

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

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

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

В первой строке входного файла записано число окон n( 1 ⩽ n ⩽ 50000 ). Следующие n строк содержат координаты окон x(1,i)y(1,i)x(2,i)y(2,i), где( x(1,i); y(1;i)) — координаты левого верхнего угла i-го окна, а( x(2;i), y(2;i)) — правого нижнего (на экране компьютера y растет сверху вниз, а x — слева направо). Все координаты — целые числа, по модулю не превосходящие 2 * 10^5.

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

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

Примеры

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

2
0 0 3 3
1 1 4 4

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

2
1 3

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

1
0 0 1 1

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

1
0 1

Решение

H. RMQ наоборот

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

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

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

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

Рассмотрим массив a[1..n]. Пусть Q(i, j) — ответ на запрос о нахождении минимума среди чисел a[i],..., a[j]. Вам даны несколько запросов и ответы на них. Восстановите исходный массив.

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

Первая строка входного файла содержит число n — размер массива, и m — число запросов ( 1 ⩽ n, m ⩽ 100 000). Следующие m строк содержат по три целых числа i, j и q, означающих, что Q(i, j) = q( 1 ⩽ _i_⩽ j ⩽ n, -2^31 ⩽ q ⩽ 2^31-1 ).

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

Если искомого массива не существует, выведите строку «inconsistent». В противном случае в первую строку выходного файла выведите «consistent». Во вторую стро- ку выходного файла выведите элементы массива. Элементами массива должны быть целые числа в интервале от -2^31 до 2^31-1 включительно. Если решений несколько, выведите любое.

Примеры

rmq.in

3 2
1 2 1
2 3 2

rmq.out

consistent
1 2 2

rmq.in

3 3
1 2 1
1 1 2
2 3 2

rmq.out

inconsistent

Решение

I. Горы

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

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

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

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

В парке развлечений «Ай-ой-ай» открылся новейший аттракцион: польские горки. Трек состоит изnрельс, присоединенных одна к концу другой. Начало первой рельсы находится на высоте 0. Оператор Петя может конфигурировать аттракцион, изменяя по своему желанию подъём несколь- ких последовательных рельс. При этом подъём всех остальных рельс не изменяется. При каждом изменении конфигурации рельс положение следующих за изменяемыми подбирается таким образом, чтобы весь трек оставался связным. Каждый запуск вагонетки осуществляется с энергией, достаточной для достижения высотыh. Это значит, что вагонетка будет двигаться до тех пор, пока высота не превысит h, либо пока не закончится трек. По записям о всех изменениях конфигурации рельс и временах запусков вагонетки для каждого запуска определите, сколько рельс вагонетка проедет до остановки. Трек можно представить как последовательность n подъемов di, по одному на рельс. Изначально рельсы горизонтальны, то есть di = 0 для всех i.

Каждое изменение конфигурации определяется числами a,b и D: все рельсы с a-й по b-ю вклю- чительно после этого действия имеют подъем, равный D.

Каждый запуск вагонетки определяется единственным целым числом h — максимальной высо- той, на которую способна подняться вагонетка.

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

В первой строке записано целое числоn( 1 ⩽ n ⩽ 10^9 ) — число рельс. Следующие строки содержат запросы трех видов:

• I a b D — изменение конфигурации. Рельсы с a-й по b-ю включительно после выполнения запроса имеют подъем, равный D.

• Q h — запуск вагонетки. Требуется найти число рельс, которое проедет вагонетка, которая способна подняться на высоту h.

• E — конец ввода. Этот запрос встретится ровно один раз в конце файла.

В любой момент времени высота любой точки трека лежит в промежутке от 0 до 10^9. Во вводе не более 100 000 строк.

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

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

Пример

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

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -
Q 3
E

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

4
1
0
3

Решение

J. Великая Китайская Стена

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

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

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

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

В этой задаче мы проследим альтернативную историю Великой Китайской Стены. Великая Китайская Стена состоит изnметровых участков, пронумерованных по порядку це лыми числами от 1 до n. Каждый участок характеризуется своей высотой в метрах — целым неот рицательным числом. До начала нашей истории Стена ещё не построена, поэтому высота каждого участка равна нулю. Происходят события двух видов.

1. УкреплениеСтены(запись: «defend a b c »). Император вызывает к себе вассалов из пригра ничных провинций и велит им сделать так, чтобы промежуток Стены, охватывающий участки от a до b включительно, имел высоту не менее c метров. Это значит, что все участки меньшей высоты на этом промежутке нужно достроить до высоты c, а остальные оставить нетронутыми. Приказ императора выполняется немедленно, то есть до наступления следующего события.
2. Нападениеварваров(запись: «attack d e»). Варвары подходят к Стене снаружи и занимают позиции напротив промежутка Стены, охватывающего участки от d до e включительно. После этого они находят такой участок на этом промежутке, у которого высота как можно мень ше, и пытаются через него проникнуть на территорию Китая. Нападение также происходит немедленно, до наступления следующего события.

Для восстановления достоверной альтернативно-исторической картины не хватает одного: для каждого нападения варваров указать минимальную высоту Стены на соответствующем промежутке, а также какой-нибудь участок из этого промежутка с такой высотой. По заданной последователь- ности событий найдите эти числа.

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

В первой строке заданы через пробел два целых числа n и m — длина Стены в метрах и ко- личество событий соответственно ( 1 ⩽ n ⩽ 10^6 , 0 ⩽ m ⩽ 10^5 ). В следующих m строках описаны события в порядке их следования. Если событие описывает укрепление Стены, оно задано в форме «defend a b c» ( 1 ⩽ a ⩽ b ⩽ n, 1 ⩽ c ⩽ 10^7 ). Если же событие описывает нападение варваров, оно задано в форме «attack d e» ( 1 ⩽ d ⩽ e ⩽ n).

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

В ответ на каждое нападение варваров выведите строку, содержащую два числа, разделённые пробелом. Первое из этих чисел — минимальная высота Стены на соответствующем промежутке. Второе — номер любого метрового участка Стены на этом промежутке, имеющего такую высоту.

Пример

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

5 4
defend 1 3 10
attack 1 4
attack 2 3
attack 1 2

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

0 4
10 2
10 1

Решение

K. Перестановка

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

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

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

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

Отображение результатов: только полное решение подзадачи будет засчитано На новый год Дед Мороз подарил НурлашКО большой массив целых чисел. Узнав это, его учитель математики решил проверить, как хорошо он освоил одну из последних тем — перестановки. Чтобы проверить это он спрашивает: «Образуют ли перестановку элементы массива c индексами от L до R включительно?» Также иногда он может изменять некоторые числа. Напомним, что перестановка из n элементов — это упорядоченный набор, состоящий из чисел 1, 2,...,n. В нашем случае n = R - L+ 1. После новогодних контестов НурлашКО еще не пришел в себя. Поэтому он попросил вас о по- мощи, чтобы не упасть в глазах своего учителя.

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

Первая строка входного файла содержит число N( 1 ⩽ N ⩽ 100 000). Во второй строке содер жатся N целых чисел a1, a2,...; aN( 1 ⩽ ai ⩽ N). Третья строка входного файла содержит число M ( 1 ⩽ M ⩽ 100 000), количество запросов учителя. В каждой из следующих M строк записано по три целых числа — t, X, Y ( 1 ⩽ t ⩽ 2 , 1 ⩽ X, Y ⩽ N). Если t равно 1, то это запрос изменения элемента, в этом случае следует выполнить присвоение a[X] = Y. Если t равно 2, то следует проверить, является ли подотрезок с индексами от X до Y перестановкой, гарантируется что X ⩽ Y.

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

Для каждого запроса второго типа в отдельной строке выведите YES если данный под отрезок является перестановкой, иначе NO.

Примеры

5
1 5 3 4 1
5
2 1 4
1 2 2
2 2 5
1 5 5
2 1 5

permutation.out

NO
YES
YES

Решение

Система оценки

Данная задача содержит шесть подзадач:

1. 1 ⩽ N, M ⩽ 1000. Оценивается в 21 балл.
2. 1 ⩽ N, M ⩽ 50 000. Оценивается в 28 баллов.
3. 1 ⩽ N, M ⩽ 100 000, при этом во всех запросах t = 2. Оценивается в 22 балла.
4. 1 ⩽ N, M ⩽100 000. Оценивается в 29 баллов.

Подзадача 2 оценивается только в случае прохождения всех тестов подзадачи 1. Подзадача 4 оценивается только в случае прохождения всех тестов подзадач 1 и 2. Подзадача 3 оценивается независимо.

L. Парковка

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

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

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

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

Hа кольцевой парковке естьnмест пронумерованых от 1 до n. Есть два вида событий прибытие машину на парковку и отъезд машины с парковки. Если машина приезжает на парковку, а её место занято, то она едет далее по кругу и встаёт на первое свободное место.

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

В первой строке входного файла находится два числа n и m — размер парковки и количество запросов( 1 ⩽ n, m ⩽ 100000 ). В следующих m строках находятся события. Каждая из этих строк имеет следующий вид:

• enter x — приехала машина, которая хочет встать на место x. Для каждой такой команды выведите какое место займёт эта машина.

• exit x — уехала машина занимавшая место x. Гарантируется, что на этом месте была машина.

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

Выведите последовательно результаты выполнения всех операций enter.

Пример

parking.in

3 5
enter 1
enter 1
exit 1
enter 2
enter 2

parking.out

1
2
3
1