Fishingprince Plays With Array Again
Contest: Codeforces Global Round 21
Difficulty rating: 3300
Tags: brute force, data structures, geometry, math

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<n$$$, decrease $$$a_i$$$ by $$$x\cdot t$$$, and decrease $$$a_{i+1}$$$ by $$$y\cdot t$$$.
- Select $$$1\le i<n$$$, 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(a)$$$.

For example, when $$$x=1$$$, $$$y=2$$$, it takes $$$3$$$ seconds to deal with the array $$$[3,1,1,3]$$$. 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([3,1,1,3])=3$$$.

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([b_l,b_{l+1},\dots,b_r])$$$.

Input format:
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,\ldots,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<r\le n$$$). It means that you should print $$$f([b_l,b_{l+1},\dots,b_r])$$$.

Output format:
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}$$$.

Constraints:
Time limit: 6.0 s
Memory limit: 1024.0 MB

Note:
Let's analyse the sample.

In the first query, we are asked to compute $$$f([3,1,1,4])$$$. The answer is $$$3.5$$$. One optimal sequence of operations is:

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

In the third query, we are asked to compute $$$f([1,1,1])$$$. The answer is $$$1$$$. One optimal sequence of operations is:

- In the first $$$0.5$$$ seconds do the second operation with $$$i=1$$$.
- In the next $$$0.5$$$ seconds do the first operation with $$$i=2$$$.

Example input:
4 3
1 2
3 1 1 4
2 1 4
1 1 1
2 1 3

Example output:
3.500000000000000
1.000000000000000

Editorial:
First we solve the problem with only 1 query on the whole array $$$A$$$.
This is a linear programming problem: $$$$$$ \text{minimize}\sum_{1\le i<n} a_i+b_i \\ Xa_1+Yb_1\ge A_1 \\ Xa_i+Yb_i+Ya_{i-1}+Xb_{i-1}\ge A_i\ (2\le i<n) \\ Ya_{n-1}+Xb_{n-1}\ge A_n \\ a_i,b_i\ge 0 $$$$$$ Consider its dual: $$$$$$ \text{maximize}\sum_{1\le i\le n}A_ix_i \\ Xx_i+Yx_{i+1}\le 1\ (1\le x<n) \\ Yx_i+Xx_{i+1}\le 1\ (1\le x<n) \\ x_i\ge 0 $$$$$$ Suppose $$$X\le Y$$$. Now we will prove that there exists an optimal solution to the dual problem, in which $$$x_i$$$ can only take three values: $$$1/Y,1/(X+Y),0$$$.
The proof is as follows: It is well-known that an optimal solution to a linear programming problem must lie on a vertex of the "multi-dimensional convex polygon" which the restrictions surround. Thus we are only interested in $$$x_i$$$ that satisfy several "=" restrictions (and the restrictions should really intersect at one point, meaning that those "=" should uniquely determine $$$x$$$). Consider any "sufficient" (that means they uniquely determine $$$\{x\}$$$) subset of them. If one restriction is related to $$$x_p,x_q$$$, we link an undirected edge between $$$p$$$ and $$$q$$$. If one restriction is only related to $$$x_p$$$ (i.e. $$$x_p=0$$$), we link a self-loop on $$$p$$$. "Being sufficient" means that all connected components in the graph has exactly one cycle. However, for an edge $$$(u,v)$$$, we know that either $$$u=v+1$$$ or $$$u=v$$$. This means that all cycles can only be $$$(i\to i+1\to i)$$$ or $$$i\to i$$$. If a cycle is $$$(i\to i+1\to i)$$$, all $$$x_i$$$ in the component are $$$1/(X+Y)$$$; If a cycle is $$$i\to i$$$, all $$$x_i$$$ in the component are $$$1/Y$$$ or $$$0$$$ (not $$$1/X$$$, because it exceeds the constraints).
Thus we can use dp to solve the dual problem. Let $$$dp(i,0/1/2)$$$ be the maximum $$$\sum_{j\le i}A_jx_j$$$ when $$$x_i$$$ is the $$$0/1/2$$$-th candidate above. Transitions are straight-forward.
For multiple queries, the transitions can be written into multiplying matrices, and we can use segment tree to maintain updates.
About precision issues: actually we can avoid using floating point numbers completely. Note that all numbers in this problem are fractions with denominator $$$Y(X+Y)$$$. Also note that the answer does not exceed $$$(\sum a_i)/Y$$$. This means that the numerator does not exceed $$$(\sum a_i)\times (X+Y)<10^{18}$$$, so we can use long long-s to only store numerators. If you use double in C++, the relative error of one operation is less than $$$10^{-15}$$$. $$$10^{-15}\times n<10^{-9}$$$, which means that using doubles is also enough.
Complexity: $$$O(n+q\log n)$$$.