Задача №3326. Количество максимумов на отрезке с изменение элемента
Реализуйте эффективную структуру данных, позволяющую изменять элементы массива и вычислять количество максимальных элементов массива из нескольких подряд идущих элементов. Входные данные В первой строке вводится одно натуральное число 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 Сдать: для сдачи задач необходимо войти в систему
|