G. Fishingprince снова играет с массивом
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Пусть дана последовательность неотрицательных целых чисел $$$a$$$ длины $$$n$$$ в 1-индексации. Также даны два целых числа $$$x$$$, $$$y$$$. В течение отрезка времени в $$$t$$$ секунд ($$$t$$$ может быть любым положительным вещественным числом) можно выполнить одну из следующих операций:

  • Выбрать $$$1\le i<n$$$, уменьшить $$$a_i$$$ на $$$x\cdot t$$$ и уменьшить $$$a_{i+1}$$$ на $$$y\cdot t$$$.
  • Выбрать $$$1\le i<n$$$, уменьшить $$$a_i$$$ на $$$y\cdot t$$$ и уменьшить $$$a_{i+1}$$$ by $$$x\cdot t$$$.

Определим $$$f(a)$$$ как минимальное количество времени (может быть вещественным числом), необходимое для того, чтобы сделать все элементы последовательности неположительными (меньше или равными $$$0$$$).

Например, если $$$x=1$$$, $$$y=2$$$, то массив $$$[3,1,1,3]$$$ можно обработать за $$$3$$$ секунды. Для этого нужно:

  • В течение первых $$$1.5$$$ секунд выполнять вторую операцию с параметром $$$i=1$$$.
  • В течение оставшихся $$$1.5$$$ секунд выполнять первую операцию с параметром $$$i=3$$$.

Можно доказать, что в этом случае невозможно сделать все элементы меньше или равными $$$0$$$ меньше чем за $$$3$$$ секунды, поэтому $$$f([3,1,1,3])=3$$$.

Вам дана последовательность положительных целых чисел $$$b$$$ длины $$$n$$$ в 1-индексации. Также даны положительные целые числа $$$x$$$, $$$y$$$. Обработайте $$$q$$$ запросов следующих двух типов:

  • 1 k v: изменить значение $$$b_k$$$ на $$$v$$$.
  • 2 l r: вывести $$$f([b_l,b_{l+1},\dots,b_r])$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$1\le q\le 2\cdot 10^5$$$).

Вторая строка содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1\le x,y\le 10^6$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_i\le 10^6$$$).

Далее следует $$$q$$$ строк. Каждая из этих $$$q$$$ строк содержит по три целых числа. Первое число $$$op$$$ равно $$$1$$$ или $$$2$$$.

  • Если оно равно $$$1$$$, далее следуют два целых числа $$$k$$$ и $$$v$$$ ($$$1\le k\le n$$$, $$$1\le v\le 10^6$$$). Такой запрос означает, что нужно изменить значение $$$b_k$$$ на $$$v$$$.
  • Если оно равно $$$2$$$, далее следуют два целых числа $$$l$$$ и $$$r$$$ ($$$1\le l<r\le n$$$). Такой запрос означает, что нужно вывести значение $$$f([b_l,b_{l+1},\dots,b_r])$$$.
Выходные данные

Для каждого запроса типа $$$2$$$ выведите одно вещественное число — ответ на этот запрос. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-9}$$$.

Пример
Входные данные
4 3
1 2
3 1 1 4
2 1 4
1 1 1
2 1 3
Выходные данные
3.500000000000000
1.000000000000000
Примечание

Разберём тестовый пример.

В первом запросе требуется вычислить $$$f([3,1,1,4])$$$. Ответ равен $$$3.5$$$. Одной из оптимальных последовательностей операций является следующая:

  • В течение первых $$$1.5$$$ секунд выполнять вторую операцию с параметром $$$i=1$$$.
  • В течение оставшихся $$$2$$$ секунд выполнять первую операцию с параметром $$$i=3$$$.

В третьем запросе требуется вычислить $$$f([1,1,1])$$$. Ответ равен $$$1$$$. Одной из оптимальных последовательностей операций является следующая:

  • В течение первых $$$0.5$$$ секунд выполнять вторую операцию с параметром $$$i=1$$$.
  • В течение оставшихся $$$0.5$$$ секунд выполнять первую операцию с параметром $$$i=2$$$.