loj#3401. 「2020-2021 集训队作业」Old Problem解题报告

解题报告

---

#3401. 「2020-2021 集训队作业」Old Problem解题报告：

dengls的题，/se。

题意

给定 $n$ 个正整数 $a_i$，$q$ 次询问，每次给定 $l,r,x$ ，求

$$1-\prod_{i=l}^r\frac{x-a_i}{x}$$

精度差在 $10^{-6}$ 以内即可。（$1\leqslant n\leqslant 6\times 10^5,1\leqslant x,a_i\leqslant 10^9$）

分析

精度题。

我么发现这个东西很难维护，于是考虑采取奇技淫巧，分治解决这一问题：

若当前递归到的区间为 $[l,r]$，那么我们查看这一区间的最大值是否不小于 $\frac{x}{2}$，若大于，则暴力计算并递归至最大值对应的左右区间，否则就玄妙计算一下，并返回。

如果我们不考虑后面，我们发现 $2^{-20}$ 约为 $9\times 10^{-7}$，已经满足精度要求，于是此处的复杂度正确。

对于后面的计算，我们可以利用的性质仅有区间最大值小于 $\frac{x}{2}$。

由于乘法太大，不好处理，套路地取 $\ln$ 后 $\exp$，我们要处理的便是：

$$\sum_{i=l}^r\ln(1-\frac{a_i}{x})$$

此时我们只要处理了 $\ln(x-a_i)$，就可以直接前缀和一波带走了。

考虑直接套用 $\ln(1-x)$ 的公式在 $x=0$ 处进行泰勒展开

$$-\sum_{i=l}^r\sum_{k}\frac{(\frac{a_i}{x})^k}{k}$$

由于区间所有数小于 $\frac{x}{2}$，所以 $\frac{a_i}{x}$ 小于 $\frac{1}{2}$，而恰好在 $x=0$ 处展若干项 $x<\frac{1}{2}$ 时精度就非常高了。

时间复杂度 $O(n\log n+q\log\frac{1}{\epsilon})$。

代码

#include<stdio.h>
#include<math.h>
const int maxn=600005,maxk=21;
int n,q,X;
int lg[maxn],a[maxn],maxx[maxn][maxk];
double ans;
double sum[maxn][maxk];
int calc(int l,int r){
    return a[l]>a[r]? l:r;
}
int query(int l,int r){
    int k=lg[r-l+1];
    return calc(maxx[l][k],maxx[r-(1<<k)+1][k]);
}
void solve(int l,int r){
    if(l>r||ans<1e-6)
        return ;
    int p=query(l,r);
    if(l==r||a[p]*2>=X){
        ans*=(1-1.0*a[p]/X);
        solve(l,p-1),solve(p+1,r);
        return ;
    }
    double res=0,mul=X;
    for(int i=1;i<=20;i++,mul*=X)
        res+=(sum[r][i]-sum[l-1][i])/mul;
    ans*=exp(-res);
}
int main(){
    scanf("%d%d",&n,&q);
    lg[0]=-1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]),maxx[i][0]=i,lg[i]=lg[i>>1]+1;
        double mul=a[i];
        for(int j=1;j<=20;j++,mul*=a[i])
            sum[i][j]=sum[i-1][j]+mul/j;
    }
    for(int i=1;i<=20;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            maxx[j][i]=calc(maxx[j][i-1],maxx[j+(1<<(i-1))][i-1]);
    for(int i=1;i<=q;i++){
        int l,r;
        scanf("%d%d%d",&l,&r,&X),ans=1;
        solve(l,r);
        printf("%.10lf\n",1-ans);
    }
    return 0;
}