Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 322 323 324 325 326 327 328 >> Отображать по:
#3312
Количество максимумов на отрезке
  
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

Примеры
Входные данные
5
2 2 2 1 5
2
2 3
2 5
Выходные данные
2 2
5 1
#3313
Количество нулей на интервале
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

Примеры
Входные данные
5
0 0 0 0 2
2
2 3
2 5
Выходные данные
2 3
#3314
НОД на подотрезках
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

Примеры
Входные данные
5
2 2 2 1 5
2
2 3
2 5
Выходные данные
2 1
#3316
Максимум на подотрезках с изменением элемента
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить максимум, u — обновить значение элемента).

Следом за s вводятся два числа — номера левой и правой границы отрезка.

Следом за u вводятся два числа — номер элемента и его новое значение.

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

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

Примеры
Входные данные
5
1 2 3 4 5
5
s 1 5
u 3 10
s 1 5
u 2 12
s 1 3
Выходные данные
5 10 12
#3317
Суммы на подотрезках с изменением элемента
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить сумму, u — обновить значение элемента).

Следом за s вводятся два числа — номера левой и правой границы отрезка.

Следом за u вводятся два числа — номер элемента и его новое значение.

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

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

Примеры
Входные данные
10
613 263 312 670 216 142 976 355 488 370
10
s 2 7
s 4 8
u 7 969
u 1 558
s 2 7
u 2 731
s 4 9
s 1 3
u 8 76
u 5 377
Выходные данные
2579 2359 2572 2840 1601
Страница: << 322 323 324 325 326 327 328 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест