Реализуйте эффективную структуру данных, позволяющую изменять элементы массивы и вычислять номер максимального элемента из нескольких подряд идущих элементов.
В первой строке вводится одно натуральное число 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
Найдите номер 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
Реализуйте эффективную структуру данных, позволяющую изменять элементы массивы и вычислять НОД нескольких подряд идущих элементов.
В первой строке вводится одно натуральное число 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
Реализуйте структуру данных для эффективного вычисления индекса 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
Реализуйте эффективную структуру данных, позволяющую изменять элементы массива и вычислять индекс 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