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

Примеры
Входные данные
5
1 2 0 2 3
3
u 2 0
s 4
s 2
Выходные данные
-1 3
#3325
Количество нулей на интервале с изменением элемента
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
5
1 2 0 2 3
3
u 2 0
s 2 4
s 3 4
Выходные данные
2 1
#3326
Количество максимумов на отрезке с изменение элемента
  
Ограничение по времени, сек1
Ограничение по памяти, мегабайт64




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

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

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

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

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

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

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

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

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

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

Примечание: Решения, верно работающие при M <= 30000, будут оцениваться в 30 баллов.
Примеры
Входные данные
5
1 3 2 3 3
5
s 1 4
u 3 3
s 1 5
u 2 1
s 1 5
Выходные данные
2 4 3
#3327
Дерево интервалов с обновлением на отрезке
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

Следом за a вводятся три числа — левый и правый концы отрезка и число add, на которое нужно увеличить все элементы данного отрезка массива (0 ≤ add ≤ 100000).

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

Выведите в одну строку через пробел ответы на каждый запрос g.

Примеры
Входные данные
5
2 4 3 5 2
5
g 2
g 5
a 1 3 10
g 2
g 4
Выходные данные
4
2
14
5
#3328
Максимум на подотрезках с добавлением на отрезке
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

Следом за a вводятся три числа — левый и правый концы отрезка и число add, на которое нужно увеличить все элементы данного отрезка массива (0 ≤ add ≤ 100000).

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

Выведите в одну строку через пробел ответы на каждый запрос m.

Примеры
Входные данные
5
2 4 3 1 5
5
m 1 3
a 2 4 100
m 1 3
a 5 5 10
m 1 5
Выходные данные
4 104 104
Страница: << 24 25 26 27 28 29 30 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест