| Условие задачи | | |
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). |
| |
![]()
|