Реализуйте эффективную структуру данных, позволяющую изменять элементы массива и вычислять индекс 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
Реализуйте эффективную структуру данных, позволяющую изменять элементы массива и вычислять количество нулей среди нескольких подряд идущих элементов.
В первой строке вводится одно натуральное число 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
Реализуйте эффективную структуру данных, позволяющую изменять элементы массива и вычислять количество максимальных элементов массива из нескольких подряд идущих элементов. Входные данные В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве. Во второй строке вводятся N чисел от 0 до 100000 — элементы массива. В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 1000000) — количество запросов. Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить количество максимумов, u — обновить значение элемента). Следом за s вводятся два числа — номера левой и правой границы отрезка. Следом за u вводятся два числа — номер элемента и его новое значение. Выходные данные Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел. Примеры Входные данные 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 ограничение по времени на тест
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 ограничение по времени на тест
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 Выбрано :
|
|