题解
显然原题等价于让我们求这个式子\(\prod\limits_{i=l}^{r}(1-p_i)\sum\limits_{i=l}^{r}\frac{p_i}{1-p_i}\)的最大值是多少
打打表，或者直观上感受一下，这东西是个凸壳，进一步观察，你会发现随着左端点的右移，最优决策点也在右移，于是拿个\(two\ pointer\)搞一搞就好了
凸性的证明在代码下面QWQ
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 1000000
int n, p[N + 5];
long double prod[N + 5], sum[N + 5], ans;
int main() {
scanf("%d", &n);
prod[0] = 1;
for (int i = 1; i <= n; ++i)
scanf("%d", &p[i]), prod[i] = p[i] / 1e6, sum[i] = sum[i - 1] + prod[i] / (1 - prod[i]), prod[i] = prod[i - 1] * (1 - prod[i]);
int j = 1;
for (int i = 1; i <= n; ++i) {
while (j + 1 <= n && prod[j + 1] * (sum[j + 1] - sum[i - 1]) >= prod[j] * (sum[j] - sum[i - 1])) j++;
ans = max(ans, prod[j] / prod[i - 1] * (sum[j] - sum[i - 1]));
}
printf("%lld\n", (long long)(ans * 1e6));
return 0;
}
证明：
①式子的值递增时，有如下不等式成立
\[\prod\limits_{i=l}^{r}(1-p_i)\sum\limits_{i=l}^{r}\frac{p_i}{1-p_i}\leqslant \prod\limits_{i=l}^{r+1}(1-p_i)\sum\limits_{i=l}^{r+1}\frac{p_i}{1-p_i}
\]
简单的化一下，会得到一个形式非常优美的东西
\[\sum\limits_{i=l}^{r}\frac{p_i}{1-p_i}\leqslant 1
\]
②式子的值递减时，同理①，可得到\(\sum\limits_{i=l}^{r}\frac{p_i}{1-p_i}\geqslant 1\)
然后又因为\(\sum\limits_{i=l}^{r}\frac{p_i}{1-p_i}\)在固定左端点并把右端点向右移动时是严格单增的，所以是凸的
有了上面的结论，也可以证明最优决策点的单调移动了