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

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

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

В первой строке вводится одно натуральное число 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
#3309
Максимумы на подотрезках
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 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 5
#3310
Индекс максимума на подотрезках
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 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 5
#3311
Левый максимум на подотрезке
  
ограничение по времени на тест
10.0 second;
ограничение по памяти на тест
256 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 5
#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
Страница: << 21 22 23 24 25 26 27 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест