## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Fishingprince Plays With Array Again Codeforces Solution

G. Fishingprince Plays With Array Again
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Suppose you are given a 1-indexed sequence $a$ of non-negative integers, whose length is $n$, and two integers $x$$y$. In consecutive $t$ seconds ($t$ can be any positive real number), you can do one of the following operations:

• Select $1\le i, decrease ${a}_{i}$ by $x\cdot t$, and decrease ${a}_{i+1}$ by $y\cdot t$.
• Select $1\le i, decrease ${a}_{i}$ by $y\cdot t$, and decrease ${a}_{i+1}$ by $x\cdot t$.

Define the minimum amount of time (it might be a real number) required to make all elements in the sequence less than or equal to $0$ as $f\left(a\right)$.

For example, when $x=1$$y=2$, it takes $3$ seconds to deal with the array $\left[3,1,1,3\right]$. We can:

• In the first $1.5$ seconds do the second operation with $i=1$.
• In the next $1.5$ seconds do the first operation with $i=3$.

We can prove that it's not possible to make all elements less than or equal to $0$ in less than $3$ seconds, so $f\left(\left[3,1,1,3\right]\right)=3$.

Solution Click Below:-  👉
👇👇👇👇👇

Now you are given a 1-indexed sequence $b$ of positive integers, whose length is $n$. You are also given positive integers $x$$y$. Process $q$ queries of the following two types:

• 1 k v: change ${b}_{k}$ to $v$.
• 2 l r: print $f\left(\left[{b}_{l},{b}_{l+1},\dots ,{b}_{r}\right]\right)$.
Input

The first line of input contains two integers $n$ and $q$ ($2\le n\le 2\cdot {10}^{5}$$1\le q\le 2\cdot {10}^{5}$).

The second line of input contains two integers $x$ and $y$ ($1\le x,y\le {10}^{6}$).

The third line of input contains $n$ integers ${b}_{1},{b}_{2},\dots ,{b}_{n}$ ($1\le {b}_{i}\le {10}^{6}$).

This is followed by $q$ lines. Each of these $q$ lines contains three integers. The first integer $op$ is either $1$ or $2$.

• If it is $1$, it is followed by two integers $k$$v$ ($1\le k\le n$$1\le v\le {10}^{6}$). It means that you should change ${b}_{k}$ to $v$.
• If it is $2$, it is followed by two integers $l$$r$ ($1\le l). It means that you should print $f\left(\left[{b}_{l},{b}_{l+1},\dots ,{b}_{r}\right]\right)$.
Output

For each query of type $2$, print one real number — the answer to the query. Your answer is considered correct if its absolute error or relative error does not exceed ${10}^{-9}$.