Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 22 23 24 25 26 27 28 >> Отображать по:
#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
#3318
Левый максимум на подотрезке с изменением элемента
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
5
2 2 1 2 2
4
s 1 3
s 1 5
u 3 2
s 2 4
Выходные данные
1 1 2
Страница: << 22 23 24 25 26 27 28 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест