Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Инверсии на отрезке#41229

Дана перестановка из n элементов.
Ответьте на m запросов про число инверсий для подотрезка перестановки от l до r.
Инверсией называется пара индексов i, j такая, что i < j и a_i > a_j, где a_i - это i-й элемент перестановки.

Входные данные:
В первой строке задано число n (1 <= n <= 10⁵).
Во второй строке задана перестановка из n элементов (элементы перестановки - попарно различные целые числа от 1 до n).
В третьей строке задано число m (1 <= m <= 10⁵).
В последующих m строках содержится по два числа l и r - границы запроса (1 <= l, r <= n).

Выходные данные:
Выведите m строк - ответы на данные запросы.

Примеры:

Входные данные	Выходные данные
5 4 5 2 3 1 3 1 3 3 5 1 5	2 2 8
6 5 2 4 3 1 6 3 4 6 2 5 1 5	1 4 8

Алгоритм Мо Дерево отрезков, RSQ, RMQ

✓ 14✗ 28900средняяВойти и решать

Сумма минимумов#39961

Вам дан массив из n целых чисел. Вам необходимо разделить его на k непустых подотрезков (последовательность подряд идущих элементов) так, чтобы:
1) Каждый элемент массива входил ровно в один подотрезок.
2) Если для каждого подотрезка выбрать минимальное в нем число, то сумма всех минимумов должна быть максимально возможной.

Сообщите сумму минимумов значений в подотрезках этого разбиения.

Входные данные:
В первой строке дается два натуральных числа - n (1 <= n <= 500) и k (1 <= k <= n).
Во второй строке дается n целых чисел - элементы массива a_i (1 <= a_i <= 10⁵).

Выходные данные:
Выведите одно число - ответ на задачу.

Пример:

Входные данные	Выходные данные
5 3 4 2 5 1 3	8

Пояснение:
Одно из подходящих разбиений: [4, 2], [5], [1, 3]. Сумма минимумов в каждом подотрезке равна 2 + 5 + 1 = 8.

Дерево отрезков, RSQ, RMQ Динамическое программирование

✓ 37✗ 305900средняяВойти и решать

Сокровища#39839

Дочь короля Флатландии собирается выйти за прекрасного принца.
Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.

В коллекции принца n бриллиантов, каждый характеризуется весом w_i и стоимостью v_i.
Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.

Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].

Входные данные:
Первая строка содержит число n (1 <= n <= 32), L и R (0 <= L <= R <= 10¹⁸).
Следующие n строк описывают бриллианты и содержат по два числа - вес и стоимость соответствующего бриллианта (1 <= wi, vi <= 10¹⁵).

Выходные данные:
Первая строка вывода должна содержать k - количество бриллиантов, которые нужно подарить принцессе.
Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.

Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.

Примеры:

Входные данные	Выходные данные
3 6 8 3 10 7 3 8 2	1 2

meet in the middle Дерево отрезков, RSQ, RMQ

✓ 163✗ 784500лёгкаяВойти и решать

Путешествие по строке#38511

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2

sqrt декомпозиция Дерево отрезков, RSQ, RMQ Динамическое программирование Суффиксный массив Хеш Хеш

✓ 1✗ 7—Войти и решать

Подстроки подпоследовательностей#38509

Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3] является попоследовательностью массива [1,2,3] , но [3,1] не является.

Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2] является подотрезком массива [1,2,3] , а [1,3] не является. Несложно заметить, что у массива длины n ровно \( {n(n+1) \over 2}\) подотрезков.

Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется a_i ≤ a_i+1.

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 10⁹+7.

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ a_i ≤ 200000) — элементы массива a.

Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 10⁹+7.

Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:

У массива [1] есть ровно один подотрезок и он является возрастающим.
У массива [2] есть ровно один подотрезок и он является возрастающим.
У массива [3] есть ровно один подотрезок и он является возрастающим.
У массива [1,2] есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
У массива [1,3] есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
У массива [3,2] есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3] и [2] ) являются возрастающими.
У массива [1,3,2] есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.

Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	15
2	3 6 6 6	12

Дерево отрезков, RSQ, RMQ Дерево Фенвика Динамическое программирование Динамическое программирование: один параметр

✓ 1✗ 1—Войти и решать

Взвешивание камней#38473

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.

Входные данные
Первая строка содержит целое число N (1 N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк - по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 2 1 4 2 5 1	< > > ? >

Алгоритмы сортировки Дерево отрезков, RSQ, RMQ Жадный алгоритм

✓ 1✗ 121 100средняяВойти и решать

Шахматные баталии#38386

Ильдар и Ваня устали постоянно играть в шахматы, поэтому они придумали новую шахматную игру.

Игра происходит на шахматном поле размером 2n×2m. Это поле имеет 2n строк и 2m столбцов. Для удобства будем обозначать как (i, j) клетку поля, которая находится в i-й строке и j-м столбце. Клетки этого поля покрашены в черный и белый цвета шахматной раскраской. Более точно, клетка (i, j) имеет белый цвет, если i + j чётно, и чёрный цвет в противном случае.

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

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

Помогите Ильдару сделать игру интересной! Напишите программу, которая будет отвечать на его запросы.

Формат входных данных
В первой строке находится три целых числа n, m, q (1 ≤ n, m, q ≤ 200 000) — количество пар строк шахматной доски, количество пар столбцов шахматной доски и количество запросов.
Следующие q строк описывают запросы Ильдара. Каждая из этих строк содержит два целых числа i, j (1 ≤ i ≤ 2n, 1 ≤ j ≤ 2m, i+j четно). Если клетка (i, j) не вырезана, то Ильдар её вырезает, иначе он возвращает её обратно на поле.

Формат выходных данных
Выведите q строк. В i-й из этих строк выведите ответ на задачу для доски, полученной после i первых запросов Ильдара.
Выведите «YES» (без кавычек), если Ваня может так расставить шахматных королей на не вырезанные белые клетки поля, что никакие два короля не будут бить друг друга. Иначе выведете «NO» (без кавычек).

Примеры

№	Входные данные	Выходные данные
1	1 3 3 1 1 1 5 2 4	YES YES NO
2	3 2 10 4 2 6 4 1 3 4 2 6 4 2 2 2 4 1 3 4 4 3 1	YES YES NO NO YES YES NO YES YES NO

Замечание
В первом примере, после второго запроса будут вырезаны клетки (1, 1) и (1, 5). Тогда Ваня может поставить три короля на клетки (2, 2), (2, 4) и (2, 6).
После третьего запроса будут вырезаны клетки (1, 1), (1, 5) и (2, 4). Тогда остаётся всего три пустые клетки (2, 2), (1, 3) и (2, 6). Ваня не может поставить трех королей на эти клетки, потому что короли в клетках (2, 2) и (1, 3) бьют друг друга, так как эти клетки соседние по углу.

Дерево отрезков, RSQ, RMQ

✓ 2✗ 31 100средняяВойти и решать

Организация коров фермера Джона 2#38136

Из N коров выбирается делегация (1≤N≤2⋅10⁵). Они стоят в ряд, корова i имеет породу b_i.

Делегация будет состоять из непрерывного участка коров не менее трёх, то есть коровы l…r для целых l и r удовлетворяющих условиям 1≤l<r≤N и r−l≥2. Три коровы в выбранном интервале помечаются как лидеры делегации. Две граничные коровы обязательно должны быть лидерами. Кроме того, каждый лидер должен иметь породу отличную от всех остальных коров в делегации (лидеры или не лидеры).

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

Входные данные:
Первая строка содержит N.
Вторая строка содержит N целых чисел b₁,b₂,…,b_N, каждое в интервале [1,N].
Выходные данные:
Количество возможных делегаций на одной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 1 2 3 4 3 2 5	9	Каждая делегация соответствует одному из следующих триплетов лидеров: (1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).

Дерево отрезков, RSQ, RMQ

✓ 1✗ 1—Войти и решать

33701#33701

Реализуйте эффективную структуру данных, позволяющую изменять элементы массивы и вычислять НОД нескольких подряд идущих элементов.

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.
Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить НОД, u — обновить значение элемента).
Следом за s вводятся два числа — номера левой и правой границы отрезка.
Следом за u вводятся два числа — номер элемента и его новое значение.

Выходные данные
Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел.

Ввод	Вывод
5 2 8 4 16 12 5 s 1 5 s 4 5 u 3 32 s 2 5 s 3 3	2 4 4 32

Дерево отрезков, RSQ, RMQ

✓ 4✗ 4—Войти и решать

Суммы на подотрезках#33700

Реализуйте структуру данных для эффективного вычисления сумм подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление суммы.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

Выходные данные
Для каждого запроса выведите сумму чисел соответствующего участка массива. Числа выводите в одну строку через пробел.

Ввод	Вывод
5 4 4 8 7 8 2 1 2 1 3	8 16

Дерево отрезков, RSQ, RMQ

✓ 57✗ 210700средняяВойти и решать

Максимумы на подотрезках#33699

Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (\(1 <= N <= 100000\)) — количество чисел в массиве. Во второй строке вводятся N чисел от 1 до 100000 — элементы массива. В третьей строке вводится одно натуральное число K (\(1 <= K <= 30000\)) — количество запросов на вычисление максимума. В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

Выходные данные
Для каждого запроса выведите значение максимального элемента на указанном отрезке массива. Числа выводите в одну строку через пробел.

Примеры

№	Входные данные	Выходные данные
1	5 2 2 2 1 5 2 2 3 2 5	2 5

sqrt декомпозиция Дерево отрезков, RSQ, RMQ

✓ 22✗ 124700средняяВойти и решать

Load Balancing#29545

Коровы Фермера Джона стоят в различных точках (x₁,y₁)…(x_n,y_n) его поля (1≤N≤100,000, все x_i и y_i - положительные нечётные целые числа, не превышающие 1,000,000. ФД хочет разделить своё поле изгородью бесконечной длины с севера на юг, описываемой уравнением x=a (a - чётное целое, так обеспечивается, что изгородь не пройдёт через позицию ни одной коровы). Также он хочет построить изгородь бесконечной длины с востока на запад, которая описывается уравнением y=b, где b - чётное целое. Эти две изгороди пересекаются в точке (a,b), и вместе делят поле на четыре региона.

ФД хочет выбрать a и b так, чтобы получить "сбалансированное" количество коров во всех регионах, т.е. чтобы не было региона, который содержит слишком много коров. Пусть M - максимальное количество коров в этих четырёх регионах, ФД хочет, чтобы M было как можно меньше. Помогите ФД определить это минимально возможное значение для M.

ФОРМАТ ВВОДА:

Первая строка ввода содержит одно целое число, N. Каждая из следующих n строк содержит местоположение одной коровы, указанное её координатами x и y.

ФОРМАТ ВЫВОДА:

Выведите минимально возможное значение M, которое может достичь ФД оптимальным расположением изгородей.

Ввод	Вывод
7 7 3 5 5 7 13 3 1 11 7 5 3 9 1	2

Дерево отрезков, RSQ, RMQ Дерево Фенвика Структуры данных Тернарный поиск

✓ 3✗ 251 100средняяВойти и решать

Trapped in the Haybales#27295

Фермер Джон получили груз из N больших стогов сена (1≤N≤100,000), и разметил их в различных положениях вдоль дороги, ведущей к амбару. К несчастью, он полностью забыл, что корова Беси пасётся вдоль дороги и может попасть в ловушку между стогами сена.

Каждый стог j имеет размер S_j и позицию Pj определяющую его положение вдоль дороги. Беси может двигаться вдоль дороги вплоть до позиции стога, но не может пересечь эту позицию. Исключение – если она прошла в этом направлении D единиц расстояния, тогда она набрала достаточно скорости, чтобы протаранить стог любого размера строго меньше чем D. Конечно после этого она может продолжить движение и таранить другие стога.

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

ФОРМАТ ВООДА:

Первая строка ввода содержит N. Каждая из последующих N строк описывает стог, и содержит два целых числа определяющих размер и позицию в диапазоне 1…10⁹. Все позиции различны.

ФОРМАТ ВЫВОДА:

Выведите одно целое число – размер области дороги, откуда Беси не сможет выбраться.

Ввод	Вывод
5 8 1 1 4 8 8 7 15 4 20	14

Дерево отрезков, RSQ, RMQ Динамическое программирование Динамическое программирование: один параметр Структуры данных

1 200средняяВойти и решать

Switch Grass#27216

Фермер Джон обнаружил, что разные типы коров любят разные типы травы. Однако он должен правильно их высаживать, чтобы не навредить.

Ферма Джона состоит из NN (1≤N≤200,000), полей, и MM пар полей соединены двунаправленными дорожками (1≤M≤200,000). Используя эти дорожки, можно пройти от любого поля к любому другому полю. Каждая дорожка имеет целочисленную длину в интервале 1…1,000,000. Любая пара полей соединена не более чем одной прямой дорожкой.

В каждом поле ФД изначально посадил один из KK типов травы (1≤K≤N). Через некоторое время, однако, он может решить изменить тип травы на некоторых из полей. Он называет это операцией "обновления".

После каждого обновления, ФД хочет знать длину кратчайшего пути между двумя полями, имеющими различные типы травы. То есть, среди всех пар полей, имеющих различные типы травы, он хочет узнать, какие два поля ближайшие друг к другу. Гарантируется, что всегда имеется как минимум одна пара полей с различными типами травы.

В 30 процентах тестов каждое поле непосредственно соединено не более чем с 10 дорожками.

ФОРМАТ ВВОДА:

Первая строка ввода содержит четыре целых числа N, M, K, Q, где Q - количество операций обновления (1≤Q≤200,000). Следующие M строк описывают дорожки. Каждая строка содержит три целых числа A, B, L, указывающих, что есть дорожка между полями A, B и её длина L. (A, B - целые числа в интервале 1…N). Следующая строка указывает начальный тип травы для каждого поля (N целых чисел в интервале 1…K). Затем идут Q строк, каждая из которых описывает одну операцию обновления двумя целыми числами A и B, означающими, что на поле A типе травы изменён на B.

ФОРМАТ ВЫВОДА:

Для каждой операции обновления выведите длину кратчайшего пути между двумя полями с различными типами травы, после применения этой операции обновления.

Ввод	Вывод
3 2 3 4 1 2 3 2 3 1 1 1 2 3 3 2 3 1 2 2 2	1 3 3 1

Алгоритмы на графах Дерево отрезков, RSQ, RMQ Минимальный каркас Обход в глубину Структуры данных

✓ 1✗ 41 200средняяВойти и решать

Рассадка зверей#24764

Сегодня Колобок созвал всех волков и лис к себе в гости на чаепитие. Чаепитие пройдет за круглым столом, за которым всего n мест. Колобок хочет рассадить зверей по-особенному — так, чтобы волки не сидели только с волками, а лисы только с лисами. Поэтому для каждого места он записал одно целое число — сколько лис должно сидеть на расстоянии не более d от этого места, включая это место.

Два места находятся на расстоянии не более d, если между ними встречаются не более d−1 места при движении по или против часовой стрелки от одного к другому. Таким образом, для заданного места всего существует 2d + 1 место, находящееся на расстоянии не более d от него.

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

Входные данные
В первой строке находятся два натуральных числа n, d (3 ≤ n ≤ 10⁵ , 3 ≤ 2d+1 ≤ n) — количество мест за круглым столом и расстояние d. В следующей строке находятся n неотрицательных целых чисел ai (0 ≤ a_i ≤ 2d+1) — количество лис на расстоянии не более d от этого места, включая это место. Информация о местах перечислена в порядке их следования по кругу.

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

Ввод	Вывод
5 1 2 2 1 2 2	YES 1 0 1 0 1
9 2 3 4 4 3 3 2 2 2 2	YES 1 0 1 1 1 0 0 0 1
6 1 3 3 3 3 3 1	NO

Дерево отрезков, RSQ, RMQ НОД и алгоритм Евклида

1 300средняяВойти и решать

Поезд#24691

Вам дан массив целочисленных чисел размера n.Необходимо реализовать структуру данных,которая могла бы исполнять следующие операции:
1)Прибавлять всем числам на отрезке [l;r] величину d.
2)Получить сумму чисел на отрезке [l;r].
3)Получить минимум из чисел на отрезке [l;r].
INPUT
На ввод приходит число n – размер массива.В следующей строке,через пробел, даны n чисел - a_i.
Далее задается число m - количество запросов.В следующих m строках запросы трех видов:
1)add l r d - прибавление на отрезке [l;r] числа d.
3)rsq l r - запрос суммы на отрезке [l;r].
3)rmq l r - запрос минимума на отрезке [l;r].
OUTPUT
Ответы для запросов второго и третьего типов через пробел.
P.S. 0 < n, m < 100001 a_i < 1000000001.
P.S.S. Гарантируется,что ответ вмещается в 64-битный тип данных.
INPUT
5
1 2 3 4 5
3
rsq 1 5
add 2 3 1
rmq 2 4
OUTPUT
15 3

(с) Никита Максимов, 2017г.

Дерево отрезков, RSQ, RMQ

✓ 1✗ 61 300средняяВойти и решать

Украшение ёлки – 2#24638

И вот вновь наступил Новый Год, и Васе снова понадобилось наряжать ёлку. Но, памятуя о своих прошлогодних неудачах (Вы о них знаете, если решали прошлогодний контест), он купил в магазине брендовые ударопрочные шарики. К сожалению, на ёлку в результате денег почти не осталось, и её пришлось покупать у какого-то индуса. Поэтому ёлка имеет форму полного двоичного дерева глубины N – на верхушке только одна ветка, и под каждой веткой, кроме самых нижних, снизу растёт ровно две. В самом низу, соответственно, под ветками только Васин немытый пол.

Но когда Вася приступил к украшению, он понял, что совершил страшную ошибку. Ударопрочные шарики были одноцветными и скучными, поэтому Вася не мог развесить их как попало, как он делал это раньше. Пришлось ему разрабатывать алгоритм украшения. Для начала он соотнёс каждому цвету его индекскрасоты – параметр от 0 до 10⁹. Чем он больше, тем более красивым кажется Васе шар этого цвета. Потом он случайным образом развесил шарики у пола (на каждую ветку Вася всегда вешает только один шар). Для всех остальных веток Вася смотрел на их нижних соседей, определял, какой из висящих на этих ветках шариков красивее, и вешал на эту ветку точно такой же.

Когда это муторное дело было наконец завершено, он посмотрел на ёлку и понял, что неудачно выбрал нижние шарики. Но Вася от этой мороки с шариками уже почти пропустил свой любимый новогодний сериал, поэтому попросил Вас помочь ему закончить украшение побыстрее.

Нижние ветви пронумерованы от 1 до 2^(N- 1), более верхним Вася из лени решил номера не давать. Вася подаёт на вход два вида запросов. В первом он заменяет какой-либо шар в нижнем уровне с номером k на шар цвета c, и хочет узнать, на скольких слоях веток (кроме нижнего) ему придётся перевесить шары, чтобы ёлка по-прежнему подходила под описанный выше алгоритм. Во втором он хочет узнать цвет самого красивого шара в секторе от l до r. К сектору относятся все ветки нижнего слоя с номерами от l до r включительно, а также все находящиеся над ними ветки.То есть, если N = 3, то к секторуот 1 до 2 относятся ветки 1 и 2, а также третья ветка, находящаяся между ними чуть выше.

Формат ввода

В первой строке задана глубина ёлки N (N<= 15) и количество запросов M (M<= 10⁷). Во второй строке задана первоначальная развеска нижних шариков, представленная их индексами красоты. В следующих M строках заданы запросыдвух типов (первый обозначен цифрой 1, а второй, как ни странно, 3). Описание запросов дано выше.

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

Нужно вывести Mстрок, содержащих ответы на запросы.

Пример

Ввод:

4 5

1 1 2 3 100 7 11 3

3 1 8

3 2 4

1 5 4

3 1 8

1 5 9

Вывод:

100

Дерево отрезков, RSQ, RMQ Префиксные суммы(минимумы, ...)

✓ 1✗ 11 200средняяВойти и решать

Assault#23586

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

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

Но Джерард не только согласился отвести свой флот из бухты Амбера, благодаря чему флоту Корвина удалось добраться до Амбера с целым и невредимым флотом, но и предоставил ему журнал с m записями, в котором в i-ой записи указано, что были перестроены сегменты с l_i по r_i, а также сказано, насколько изменилась укрепленность всех сегментов (укрепленность каждого сегмента на отрезке [li; ri] изменяется на одно и тоже значение t_i).

Корвин m раз предлагает выстрелить по сегментам стены с l по r из p кораблей. Известно, что брешь будет пробита, если на отрезке [l; r] есть хотя бы один сегмент с укрепленностью меньше p. Вы должны ответить ему, будет ли пробита брешь (вывести "YES"), или нет (вывести "NO").

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

На первой строке находятся числа n, m и k (1 <= n, k <= 100000, 1 <= m <= 10000) - количество сегментов, записей и запросов от Корвина соответственно.

На второй строке находятся числа a₁,..., a_n (0 <= a_i <= 10).

В следующих m строках содержатся числа l, r, t (1 <= l <= r <= n, -10 <= t <= 10).

В следующих k строках содержатся числа l, r, p (1 <= l <= r <= n, 1 <= p <= 1000).

Выходные данные
В i-ой строке выведите ответ на i-ый запрос Корвина.

Примеры

№	Входные данные	Выходные данные
1	10 3 3 123 398 287 190 76 15 407 312 323 659 4 9 -99 10 10 -82 4 10 76 9 10 32 5 6 283 4 4 983	NO YES YES

Дерево отрезков, RSQ, RMQ Префиксные суммы(минимумы, ...)

✓ 33✗ 111700средняяВойти и решать

Siege#23585

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

Блейз и Джулиан строят свои отряды стрелков в линии и дают каждому отряду номер от 1 до n. У каждого отряда есть своя сила, которая выражается некоторым натуральным числом.

Напротив отряда Джулиана с номером i стоит отряд Блейза с номером i. Далее следует m приказов:

Джулиан приказывает отрядам с номерами от l₁ до r₁ дать залп по стоящим напротив них отрядам Блейза.

В то время, пока стрелки Джулиана перезаряжаются, Блейз приказывает отрядам с номерами от l₂ до r₂ дать залп по стоящим напротив стрелкам Джулиана.

После этого все повторяется: Джулиан дает залп, Блейз дает залп и т.д.

Сила залпа и защита вычисляются как сумма сил солдат на отрезке [l; r]. Если сила залпа оказывается выше защиты, то все защищающиеся отряды уничтожаются и больше не могут стрелять (их сила больше не учитывается при подсчете защиты и силы залпа).

Вам даны приказы командиров. Ваша задача узнать, чья армия победила. Победившей считается армия, которая после последнего приказа может уничтожить армию противника, т.е. сила залпа на отрезке [1; n] победившей армии больше, чем защита проигравшей армии на отрезке [1; n].

Если победил Блейз, то выведите "Bleys" (без кавычек).

Иначе выведите "Julian" (без кавычек). Также выведите разницу между силой залпа победившей армии и защитой проигравшей.

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

В первой строке находятся числа n и m (1 <= n, m <= 100000) - количество отрядов у Блейза и Джулиана и количество отданных приказов.

Во второй строке находятся n чисел a₁, a₂, ..., a_n (1 <= a_i <= 1000) - сила отрядов Джулиана.

В третьей строке находятся n чисел b₁, b₂, ..., b_n (1 <= bi <= 1000) - сила отрядов Блейза.

В следующих m строках находятся числа l и r (1 <= l <= r <= n) - отданные приказы.

Выходные данные
Выведите "Bleys", если победил Блейз. Иначе выведите "Julian". Также выведите число - разницу между силой залпа и защитой.

Примеры

№	Входные данные	Выходные данные
1	10 3 2 2 4 9 1 8 6 1 8 8 1 1 8 9 3 6 5 1 8 6 5 9 1 6 9 10	Julian 30

Дерево отрезков, RSQ, RMQ

✓ 25✗ 96800средняяВойти и решать

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

Корвин и Блейз готовятся ко вторжению в Амбер, чтобы свергнуть Эрика. Для этого им нужно собрать армию. В мире, где они находятся есть n поселений, расположенных в линию из-за особенностей местности. Известно, что в первом поселении есть a₁ воинов, во втором - a₂, в i-ом - a_i, в n-ом - a_n.

Иногда Корвин и Блейз узнают, что в a_i поселении иное количество воинов, чем предполагалось. Корвин и Блейз спрашивают вас m раз, какое максимальное количество воинов, имеющееся в каком-либо поселении может предоставить наибольшее число воинов. Помогите им определить это.

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

В первой строке на вход подаются числа n и m (1 <= n, m <= 100000) - число поселений и число запросов.

Во второй строке находятся n чисел a₁, a₂, ..., a_n (1 <= a_i <= 1000) - количество воинов в поселениях.

В следующих m строках находятся числа t, l и r (1 <= l <= r <= n), (0 <= t <= 1) - если t равно 0, то l и r - границы запросов. Иначе l - номер города, а r - новая информация.

Выходные данные
На i-той строке выведите ответ на i-тый запрос, если t_i=0, иначе выведите "-1".

Примеры

№	Входные данные	Выходные данные
1	5 3 1 2 3 4 5 0 1 5 1 3 6 0 1 5	5 -1 6

Дерево отрезков, RSQ, RMQ

✓ 59✗ 158700средняяВойти и решать