关于一类误差分析题。之前学这东西以为这辈子不会用到，结果 NOIP 模拟赛 T2 考了，结果 std 还是假的。
例题 「2020-2021 集训队作业」Old Problem
不难发现是多次查区间 \(\prod (1-\frac {a_i} x)\) 的值，满足 \(x,a_i\in [1,10^9],x>\max a_i\)
我们记 \(eps\) 为题目要求的精度。
发现这东西很难维护，对于求乘积，不难想到先 \(\ln\) 再 \(\exp\) 回去，因为题目只要求答案在精度范围内正确，于是我们考虑对每项泰勒展开，将 \(\ln(1-x)=-\sum \frac {x^i} i\) 代入。
然后因为在原题数据范围下 \(x\in(0,1)\)，这个式子在 \(i>\log_{\frac 1 x} eps^{-1}\) 时小于 \(eps\)，但在 \(x\) 接近 \(1\) 时我们所需的项数是与 \(n\) 同阶的。
考虑取一个阈值 \(R\)，例如 \(R=0.5\)，假如 \(x>R\)，那么有 \(1-x<1-R\)，这样的数我们乘 \(\log_{\frac 1 {1-R}} eps^{-1}\) 个过后答案就会 \(<eps\)，直接输出 \(0\) 即可，对于静态的问题，我们可以用 ST 表维护区间最大值的位置，剩下的部分我们维护泰勒展开 \(\log_{\frac 1 R} eps^{-1}\) 位的前缀和即可。
对于动态的问题，我们在线段树上维护区间最大值的值和位置以及泰勒展开对应位的和即可。
分析一下复杂度，带修时精细实现是 \(O(n\log n \log eps^{-1})\) 的，不带修可以做到 \(n(\log n + \log eps^{-1})\)。
鲜花
模拟赛考的是这题的带修版本，但是 std 写的泰勒展开一百次，聪明的出题人数据特地没造有位置值接近 \(1\) 的数据，并且造了泰勒展开一百次能过，但低于一百次无法通过的数据。