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

6 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Минимум на отрезке#55364
Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.

Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤  N ≤  150000, 1 ≤ K ≤ 10000, K ≤  N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.
ДекДерево отрезков, RSQ, RMQ
✓ 13✗ 3600лёгкаяВойти и решать
Сокровища#39839
Дочь короля Флатландии собирается выйти за прекрасного принца. 
Принц хочет подарить принцессе сокровища, но он не уверен какие именно бриллианты из своей коллекции выбрать.

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

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

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

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

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

Примеры:
 
Входные данные Выходные данные
3 6 8
3 10
7 3
8 2		 1
2
meet in the middleДерево отрезков, RSQ, RMQ
✓ 163✗ 784500лёгкаяВойти и решать
Суммы на подотрезках#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средняяВойти и решать
Assault#23586
В то время, пока обороняющиеся отвлеклись на Блейза, Корвин начал штурм города. Для того, чтобы его армия вошла в город, ему нужно пробить брешь в стене. В его распоряжении есть целый флот, из которого он собирается обстреливать стены города. Стена являются линией из n сегментов, пронумерованных от 1 до n. 
Корвин хорошо помнит, насколько укреплен каждый сегмент стены. К сожалению, с тех пор как Корвин последний раз был в Амбере, сегменты несколько раз перестраивали, поэтому их укрепленность могла измениться, поэтому Корвин владеет устаревшей информацией.
Но Джерард не только согласился отвести свой флот из бухты Амбера, благодаря чему флоту Корвина удалось добраться до Амбера с целым и невредимым флотом, но и предоставил ему журнал с m записями, в котором в i-ой записи указано, что были перестроены сегменты с li по ri, а также сказано, насколько изменилась укрепленность всех сегментов (укрепленность каждого сегмента на отрезке [li; ri] изменяется на одно и тоже значение ti).
Корвин m раз предлагает выстрелить по сегментам стены с l по r из p кораблей. Известно, что брешь будет пробита, если на отрезке [l; r] есть хотя бы один сегмент с укрепленностью меньше p. Вы должны ответить ему, будет ли пробита брешь (вывести "YES"), или нет (вывести "NO"). 

Входные данные
На первой строке находятся числа n, m и k (1 <= n, k <= 100000, 1 <= m <= 10000)  - количество сегментов, записей и запросов от Корвина соответственно.
На второй строке находятся числа a1,..., an (0 <= ai <= 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средняяВойти и решать
Дерево отрезков#23581
Корвин и Блейз готовятся ко вторжению в Амбер, чтобы свергнуть Эрика. Для этого им нужно собрать армию. В мире, где они находятся есть n поселений, расположенных в линию из-за особенностей местности. Известно, что в первом поселении есть a1 воинов, во втором - a2, в i-ом - ai, в n-ом - an. 
Иногда Корвин и Блейз узнают, что в ai поселении иное количество воинов, чем предполагалось. Корвин и Блейз спрашивают вас m раз, какое максимальное количество воинов, имеющееся в каком-либо поселении может предоставить наибольшее число воинов. Помогите им определить это.

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

Выходные данные
На i-той строке выведите ответ на i-тый запрос, если ti=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средняяВойти и решать
Поделиться
Класснуть