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

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
5
2 4 1 3 5
3
s 2 4
u 1 10
s 1 3
Выходные данные
2 1
#3320
k-й ноль
  

Найдите номер k-го слева нулевого элемента массива.

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

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

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

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

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

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

Выведите в строчку через пробел M чисел — индексы искомых элементов.

Примеры
Входные данные
7
2 0 3 0 0 2 0
3
1
4
5
Выходные данные
2 7 -1
#3321
НОД на подотрезках с изменением элемента
  
ограничение по времени на тест
2.5 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводится одно натуральное число 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
#3322
k-й ноль на интервале
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

Примеры
Входные данные
5
0 0 2 0 1
5
1 5 2
2 4 2
3 5 3
1 1 1
3 4 1
Выходные данные
2 4 -1 1 4
#3323
k-й ноль на интервале, c изменением элемента
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

Следом за s вводится три числа — левый и правый концы интервала и число k (1 ≤ k ≤ N).

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

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

Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел. Если на запрашиваемом интервале нулей меньше, чем k, выводите -1 для данного запроса.

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