假设给你一个 1 索引的非负整数序列 $$$a$$$,其长度为 $$$n$$$,以及两个整数 $$$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}$$$减少$$$x\cdot t$$$。
定义使序列中所有元素小于或等于$$$0$$$所需的最短时间(可能是实数)为$$$f(a)$$$。
例如,当$$$x=1$$$、$$$y=2$$$时,处理数组$$$[3,1,1,3]$$$需要$$$3$$$秒。我们可以:
- 在第一个 $$$1.5$$$ 秒内使用 $$$i=1$$$ 执行第二个操作。
- 在接下来的 $$$1.5$$$ 秒内使用 $$$i=3$$$ 执行第一个操作。
我们可以证明,不可能在$$$3$$$秒内让所有元素都小于或等于$$$0$$$,所以$$$f([3,1,1,3])=3$$$。
现在给你一个 1 索引的正整数序列 $$$b$$$,其长度为 $$$n$$$。您还会获得正整数 $$$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}$$$,则视为正确。
示例
输入 #1
4 3 1 2 3 1 1 4 2 1 4 1 1 1 2 1 3
输出 #1
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$$$ 执行第一个操作。