Сканер силы на арене

В игре есть длинная арена из N клеток. В каждой клетке стоит энергетический тотем с силой A[i].

Во время матча ведущий делает запросы двух типов:

• меняет силу одного тотема;
• просит назвать самую сильную клетку на отрезке арены.

Тебе нужно быстро отвечать на все запросы.

Формат ввода

Первая строка: два целых числа N и Q — число клеток и число запросов. Вторая строка: N целых чисел A[1], A[2], ..., A[N]. Далее Q строк, каждая — один запрос:

• U i x — установить A[i] = x;
• Q l r — вывести максимальное значение среди A[l..r].

Формат вывода

Для каждого запроса вида Q l r выведи одно число — максимум на отрезке.

Ограничения

• 1 ≤ N ≤ 65000
• 1 ≤ Q ≤ 65000
• -1000000 ≤ A[i], x ≤ 1000000
• 1 ≤ i ≤ N
• 1 ≤ l ≤ r ≤ N

Пример

Ввод:

5 7
1 3 -2 7 4
Q 2 5
U 3 10
Q 1 3
Q 3 3
U 5 -5
Q 4 5
Q 1 5

Вывод:

7
10
10
7
10

Ключевое наблюдение: после изменения A[i] пересчитывать максимум на каждом запросе простым проходом по отрезку нельзя — в худшем случае это O(N) на запрос. При 65000 запросах получится слишком много операций.

Нужно дерево отрезков. Это двоичное дерево, где каждая вершина отвечает за некоторый непрерывный кусок массива и хранит максимум на нём. Лист хранит одно значение A[i], а его родитель — max(левый_сын, правый_сын). Значит, если меняется один элемент, затронуты только его лист и вершины на пути к корню.

• Выберите размер нижнего уровня: ближайшую степень двойки, не меньшую N.
• Поместите значения массива в листья. Пустые листья заполните очень маленьким числом, например -10**18: значения могут быть отрицательными.
• Постройте внутренние вершины снизу вверх, записывая max(seg[2*v], seg[2*v+1]).
• Для U i x замените соответствующий лист, затем поднимайтесь к корню и пересчитывайте максимумы.
• Для Q l r поднимайте границы отрезка по дереву. Если текущая левая граница — правый сын, её кусок целиком входит в ответ; аналогично для правой границы, если она левый сын.

Каждая операция проходит лишь по высоте дерева, поэтому построение занимает O(N), а один запрос или обновление — O(log N).

Грабли: в вводе индексы начинаются с 1, а массивы Python — с 0. Также обычное дерево Фенвика для максимумов здесь неудобно: значение разрешено не только увеличивать, но и уменьшать, а максимум после уменьшения нельзя быстро «вычесть» из накопленных данных.