309546: CF1696G. Fishingprince Plays With Array Again
Memory Limit：1024 MB
Time Limit：6 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Fishingprince Plays With Array Again
题意翻译
定义关于两个参数 $X$，$Y$ 的对于序列 $a$ 的函数 $f(a)$： 你可以对序列从 $1$ 开始长度为 $n$ 的 $a$ 进行以下两种操作： 1. 在位置 $i\ (1\le i<n)$ 花费 $t$ 秒，使 $a_i\gets a_i-Xt,a_{i+1}\gets a_i-Yt$。 2. 在位置 $i\ (1\le i<n)$ 花费 $t$ 秒，使 $a_i\gets a_i-Yt,a_{i+1}\gets a_i-Xt$。 $f(a)$ 为通过上述两个操作使得 $a$ 序列中所有元素小于等于 $0$ 所需要花费的最小时间。 给定参数 $X$，$Y$ 与序列 $a$，每次进行下列两个操作中的一个： 1. `1 k v` 将 $a_k$ 变为 $v$。 2. `2 l r` 将 $a$ 序列中 $[l,r]$ 区间范围内的元素以原顺序取出作为序列 $b$，求 $f(b)$。题目描述
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]) $ .输入输出格式
输入格式
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]) $ .
输出格式
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} $ .
输入输出样例
输入样例 #1
4 3
1 2
3 1 1 4
2 1 4
1 1 1
2 1 3输出样例 #1
3.500000000000000
1.000000000000000说明
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 $ .Input
题意翻译
定义关于两个参数 $X$，$Y$ 的对于序列 $a$ 的函数 $f(a)$： 你可以对序列从 $1$ 开始长度为 $n$ 的 $a$ 进行以下两种操作： 1. 在位置 $i\ (1\le i<n)$ 花费 $t$ 秒，使 $a_i\gets a_i-Xt,a_{i+1}\gets a_i-Yt$。 2. 在位置 $i\ (1\le i<n)$ 花费 $t$ 秒，使 $a_i\gets a_i-Yt,a_{i+1}\gets a_i-Xt$。 $f(a)$ 为通过上述两个操作使得 $a$ 序列中所有元素小于等于 $0$ 所需要花费的最小时间。 给定参数 $X$，$Y$ 与序列 $a$，每次进行下列两个操作中的一个： 1. `1 k v` 将 $a_k$ 变为 $v$。 2. `2 l r` 将 $a$ 序列中 $[l,r]$ 区间范围内的元素以原顺序取出作为序列 $b$，求 $f(b)$。Output
**标题：Fishingprince Plays With Array Again**
**题意翻译：**
定义一个关于两个参数 $X$、$Y$ 的函数 $f(a)$，作用于序列 $a$：
可以对长度为 $n$ 的序列 $a$ 从 $1$ 开始进行以下两种操作：
1. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Xt, a_{i+1} \gets a_i - Yt$。
2. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Yt, a_{i+1} \gets a_i - Xt$。
$f(a)$ 是通过上述两个操作使得 $a$ 序列中所有元素小于等于 $0$ 所需要花费的最小时间。
给定参数 $X$、$Y$ 与序列 $a$，每次进行以下两个操作中的一个：
1. `1 k v` 将 $a_k$ 变为 $v$。
2. `2 l r` 将 $a$ 序列中 $[l,r]$ 区间范围内的元素以原顺序取出作为序列 $b$，求 $f(b)$。
**题目描述：**
给定一个长度为 $n$ 的非负整数序列 $a$，索引从 $1$ 开始，以及两个整数 $x$、$y$。在连续的 $t$ 秒内（$t$ 可以是任意正实数），你可以执行以下任一操作：
- 选择 $1 \leq i < n$，将 $a_i$ 减少 $x \cdot t$，并将 $a_{i+1}$ 减少 $y \cdot t$。
- 选择 $1 \leq 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$。
现在给定一个长度为 $n$ 的正整数序列 $b$，索引从 $1$ 开始，以及两个正整数 $x$、$y$。处理 $q$ 次以下两种类型的查询：
- `1 k v`：将 $b_k$ 变为 $v$。
- `2 l r`：打印 $f([b_l,b_{l+1},\ldots,b_r])$。
**输入输出格式：**
**输入格式：**
第一行输入包含两个整数 $n$ 和 $q$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$）。
第二行输入包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq 10^6$）。
第三行输入包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^6$）。
接下来是 $q$ 行。每行包含三个整数。第一个整数 $op$ 要么是 $1$ 要么是 $2$。
- 如果是 $1$，后面跟着两个整数 $k$、$v$（$1 \leq k \leq n$，$1 \leq v \leq 10^6$）。这意味着你应该将 $b_k$ 变为 $v$。
- 如果是 $2$，后面跟着两个整数 $l$、$r$（$1 \leq l < r \leq n$）。这意味着你应该打印 $f([b_l, b_{l+1}, \ldots, b_r])$。
**输出格式：**
对于每个类型为 $2$ 的查询，打印一个实数——查询的答案。如果您的答案的绝对误差或相对误差不超过 $10^{-9}$，则认为答案是正确的。
**输入输出样例：**
**输入样例 #1：**
```
4 3
1 2
3 1 1**标题：Fishingprince Plays With Array Again** **题意翻译：** 定义一个关于两个参数 $X$、$Y$ 的函数 $f(a)$，作用于序列 $a$： 可以对长度为 $n$ 的序列 $a$ 从 $1$ 开始进行以下两种操作： 1. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Xt, a_{i+1} \gets a_i - Yt$。 2. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Yt, a_{i+1} \gets a_i - Xt$。 $f(a)$ 是通过上述两个操作使得 $a$ 序列中所有元素小于等于 $0$ 所需要花费的最小时间。 给定参数 $X$、$Y$ 与序列 $a$，每次进行以下两个操作中的一个： 1. `1 k v` 将 $a_k$ 变为 $v$。 2. `2 l r` 将 $a$ 序列中 $[l,r]$ 区间范围内的元素以原顺序取出作为序列 $b$，求 $f(b)$。 **题目描述：** 给定一个长度为 $n$ 的非负整数序列 $a$，索引从 $1$ 开始，以及两个整数 $x$、$y$。在连续的 $t$ 秒内（$t$ 可以是任意正实数），你可以执行以下任一操作： - 选择 $1 \leq i < n$，将 $a_i$ 减少 $x \cdot t$，并将 $a_{i+1}$ 减少 $y \cdot t$。 - 选择 $1 \leq 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$。 现在给定一个长度为 $n$ 的正整数序列 $b$，索引从 $1$ 开始，以及两个正整数 $x$、$y$。处理 $q$ 次以下两种类型的查询： - `1 k v`：将 $b_k$ 变为 $v$。 - `2 l r`：打印 $f([b_l,b_{l+1},\ldots,b_r])$。 **输入输出格式：** **输入格式：** 第一行输入包含两个整数 $n$ 和 $q$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$）。 第二行输入包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq 10^6$）。 第三行输入包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^6$）。 接下来是 $q$ 行。每行包含三个整数。第一个整数 $op$ 要么是 $1$ 要么是 $2$。 - 如果是 $1$，后面跟着两个整数 $k$、$v$（$1 \leq k \leq n$，$1 \leq v \leq 10^6$）。这意味着你应该将 $b_k$ 变为 $v$。 - 如果是 $2$，后面跟着两个整数 $l$、$r$（$1 \leq l < r \leq n$）。这意味着你应该打印 $f([b_l, b_{l+1}, \ldots, b_r])$。 **输出格式：** 对于每个类型为 $2$ 的查询，打印一个实数——查询的答案。如果您的答案的绝对误差或相对误差不超过 $10^{-9}$，则认为答案是正确的。 **输入输出样例：** **输入样例 #1：** ``` 4 3 1 2 3 1 1
**题意翻译：**
定义一个关于两个参数 $X$、$Y$ 的函数 $f(a)$，作用于序列 $a$：
可以对长度为 $n$ 的序列 $a$ 从 $1$ 开始进行以下两种操作：
1. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Xt, a_{i+1} \gets a_i - Yt$。
2. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Yt, a_{i+1} \gets a_i - Xt$。
$f(a)$ 是通过上述两个操作使得 $a$ 序列中所有元素小于等于 $0$ 所需要花费的最小时间。
给定参数 $X$、$Y$ 与序列 $a$，每次进行以下两个操作中的一个：
1. `1 k v` 将 $a_k$ 变为 $v$。
2. `2 l r` 将 $a$ 序列中 $[l,r]$ 区间范围内的元素以原顺序取出作为序列 $b$，求 $f(b)$。
**题目描述：**
给定一个长度为 $n$ 的非负整数序列 $a$，索引从 $1$ 开始，以及两个整数 $x$、$y$。在连续的 $t$ 秒内（$t$ 可以是任意正实数），你可以执行以下任一操作：
- 选择 $1 \leq i < n$，将 $a_i$ 减少 $x \cdot t$，并将 $a_{i+1}$ 减少 $y \cdot t$。
- 选择 $1 \leq 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$。
现在给定一个长度为 $n$ 的正整数序列 $b$，索引从 $1$ 开始，以及两个正整数 $x$、$y$。处理 $q$ 次以下两种类型的查询：
- `1 k v`：将 $b_k$ 变为 $v$。
- `2 l r`：打印 $f([b_l,b_{l+1},\ldots,b_r])$。
**输入输出格式：**
**输入格式：**
第一行输入包含两个整数 $n$ 和 $q$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$）。
第二行输入包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq 10^6$）。
第三行输入包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^6$）。
接下来是 $q$ 行。每行包含三个整数。第一个整数 $op$ 要么是 $1$ 要么是 $2$。
- 如果是 $1$，后面跟着两个整数 $k$、$v$（$1 \leq k \leq n$，$1 \leq v \leq 10^6$）。这意味着你应该将 $b_k$ 变为 $v$。
- 如果是 $2$，后面跟着两个整数 $l$、$r$（$1 \leq l < r \leq n$）。这意味着你应该打印 $f([b_l, b_{l+1}, \ldots, b_r])$。
**输出格式：**
对于每个类型为 $2$ 的查询，打印一个实数——查询的答案。如果您的答案的绝对误差或相对误差不超过 $10^{-9}$，则认为答案是正确的。
**输入输出样例：**
**输入样例 #1：**
```
4 3
1 2
3 1 1**标题：Fishingprince Plays With Array Again** **题意翻译：** 定义一个关于两个参数 $X$、$Y$ 的函数 $f(a)$，作用于序列 $a$： 可以对长度为 $n$ 的序列 $a$ 从 $1$ 开始进行以下两种操作： 1. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Xt, a_{i+1} \gets a_i - Yt$。 2. 在位置 $i$（$1 \leq i < n$）花费 $t$ 秒，使得 $a_i \gets a_i - Yt, a_{i+1} \gets a_i - Xt$。 $f(a)$ 是通过上述两个操作使得 $a$ 序列中所有元素小于等于 $0$ 所需要花费的最小时间。 给定参数 $X$、$Y$ 与序列 $a$，每次进行以下两个操作中的一个： 1. `1 k v` 将 $a_k$ 变为 $v$。 2. `2 l r` 将 $a$ 序列中 $[l,r]$ 区间范围内的元素以原顺序取出作为序列 $b$，求 $f(b)$。 **题目描述：** 给定一个长度为 $n$ 的非负整数序列 $a$，索引从 $1$ 开始，以及两个整数 $x$、$y$。在连续的 $t$ 秒内（$t$ 可以是任意正实数），你可以执行以下任一操作： - 选择 $1 \leq i < n$，将 $a_i$ 减少 $x \cdot t$，并将 $a_{i+1}$ 减少 $y \cdot t$。 - 选择 $1 \leq 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$。 现在给定一个长度为 $n$ 的正整数序列 $b$，索引从 $1$ 开始，以及两个正整数 $x$、$y$。处理 $q$ 次以下两种类型的查询： - `1 k v`：将 $b_k$ 变为 $v$。 - `2 l r`：打印 $f([b_l,b_{l+1},\ldots,b_r])$。 **输入输出格式：** **输入格式：** 第一行输入包含两个整数 $n$ 和 $q$（$2 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$）。 第二行输入包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq 10^6$）。 第三行输入包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^6$）。 接下来是 $q$ 行。每行包含三个整数。第一个整数 $op$ 要么是 $1$ 要么是 $2$。 - 如果是 $1$，后面跟着两个整数 $k$、$v$（$1 \leq k \leq n$，$1 \leq v \leq 10^6$）。这意味着你应该将 $b_k$ 变为 $v$。 - 如果是 $2$，后面跟着两个整数 $l$、$r$（$1 \leq l < r \leq n$）。这意味着你应该打印 $f([b_l, b_{l+1}, \ldots, b_r])$。 **输出格式：** 对于每个类型为 $2$ 的查询，打印一个实数——查询的答案。如果您的答案的绝对误差或相对误差不超过 $10^{-9}$，则认为答案是正确的。 **输入输出样例：** **输入样例 #1：** ``` 4 3 1 2 3 1 1