| Условие задачи | | |
ID 33700: Суммы на подотрезках
Темы:
Дерево отрезков, RSQ, RMQ
Реализуйте структуру данных для эффективного вычисления сумм подряд идущих элементов массива.
Входные данные
В первой строке вводится одно натуральное число 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 |
| |
![]()
|
ID 33701:
Темы:
Дерево отрезков, RSQ, RMQ
Реализуйте эффективную структуру данных, позволяющую изменять элементы массивы и вычислять НОД нескольких подряд идущих элементов.
Входные данные
В первой строке вводится одно натуральное число 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 |
| |
![]()
|
ID 33699: Максимумы на подотрезках
Темы:
Дерево отрезков, RSQ, RMQ
Корневая эвристика (sqrt декомпозиция)
Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.
Входные данные
В первой строке вводится одно натуральное число 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 |
| |
![]()
|
ID 38136: Организация коров фермера Джона 2
Темы:
Дерево отрезков, RSQ, RMQ
Из N коров выбирается делегация (1≤N≤2⋅105). Они стоят в ряд, корова i имеет породу bi.
Делегация будет состоять из непрерывного участка коров не менее трёх, то есть коровы l…r для целых l и r удовлетворяющих условиям 1≤l<r≤N и r−l≥2. Три коровы в выбранном интервале помечаются как лидеры делегации. Две граничные коровы обязательно должны быть лидерами. Кроме того, каждый лидер должен иметь породу отличную от всех остальных коров в делегации (лидеры или не лидеры).
Определите количество способов которыми можно выбрать делегацию. Две делегации рассматриваются различными, если у них отличаются члены или лидеры.
Входные данные:
Первая строка содержит N.
Вторая строка содержит N целых чисел b1,b2,…,bN, каждое в интервале [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). |
| |
![]()
|
ID 38473: Взвешивание камней
Темы:
Алгоритмы сортировки
Дерево отрезков, RSQ, RMQ
Жадный алгоритм
Джек нашел 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 |
<
>
>
?
>
|
| |
![]()
|
ID 38509: Подстроки подпоследовательностей
Темы:
Динамическое программирование: один параметр
Динамическое программирование
Дерево отрезков, RSQ, RMQ
Дерево Фенвика
Назовем подпоследовательностью массива 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 выполняется ai ≤ ai+1.
Монотонностью массива назовем количество его возрастающих подотрезков.
Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 109+7.
Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ ai ≤ 200000) — элементы массива a.
Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 109+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 |
| |
![]()
|
ID 38511: Путешествие по строке
Темы:
Дерево отрезков, RSQ, RMQ
Корневая эвристика (sqrt декомпозиция)
Хеш
Суффиксный массив
Динамическое программирование
Хеш
Скажем, что последовательность строк t1 , ..., tk является путешествием длины k , если для всех i > 1 ti является подстрокой ti - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.
Определим путешествие по строке s как путешествие t1 , ..., tk , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u1 , ..., uk + 1 , такие, что s = u1t1u2 t2 ... uk tk uk + 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 |
| |
![]()
|