题目描述

大厨住的城市里办了一场美食节。一条街上开设了\(N\)个摊位,编号为\(1 ∼ N\)。这天开始时，

第\(i\)个摊位的食物会导致食物中毒的概率是\(P_i\)。

在这一天中，大厨发现某些摊位可能会根据顾客的反馈提供没那么有毒的食物。你需要处理

\(Q\)个询问，询问有以下两类：

• 0 L R：求出：如果要吃遍\([L, R]\)内所有摊位的食物，那么不会食物中毒的概率是多少；

• 1 L R T：\[[L, R]\]中的所有摊位的食物会导致食物中毒的概率变为了原来的\(T\)倍。\(T\)是一

个小于 1 的非负实数。

数据范围

• \(1 ≤ N, Q ≤ 10^5\)

• \(0 ≤ Pi ≤ 0.9\) \(T<1\)

• \(1 ≤ L ≤ R ≤ N\)

解题思路

发现这个东西特别不好维护......

\[ ans=\prod_{i=L}^{R}(1-p_i)=e^{ln\prod_{i=L}^{R}(1-p_i)}=e^{\sum_{i=L}^{R}ln(1-p_i)} \]

上面就是正解的转化,因为\(ln\)这个函数特别好泰勒展开

什么是泰勒展开,就是一个复杂的函数我们用一个多项式拟合

思考的过程就是对于一个点\(x_0\),这个点\(g(x_0)=f(x_0),g'(x_0)=f'(x_0),g''(x_0)=f''(x_0)…\)于是推出

\[ f(x)=\sum_{i=0}^{n}\frac{f^{(i)}(x_0)}{i!}(x-x_0)i \]

回到这题,我们对\(ln(1-x)\)泰勒展开,为了简便我们使\(x_0=0\),于是不难转化成

\[ ln(1-x)=-\sum_{i=1}^{\infty}\frac{x^i}{i} \]

所以直接线段树维护即可.

#include
    
     #include
     
      #define ls (x<<1)#define rs ((x<<1)+1)using namespace std;const int maxn=100005,W=100;double a[maxn<<2][W],tag[maxn<<2],p[maxn];int n,m;void up(int x){for (int i=1;i
      
       >1);Build(ls,L,mid);Build(rs,mid+1,R);up(x);}void pushdown(int x){add(ls,tag[x]);add(rs,tag[x]);tag[ls]*=tag[x];tag[rs]*=tag[x];tag[x]=1;}void change(int x,int l,int r,int L,int R,double T){    if (l
       
        >1);    if (R<=mid) change(ls,l,mid,L,R,T);else    if (L>mid) change(rs,mid+1,r,L,R,T);else    change(ls,l,mid,L,mid,T),change(rs,mid+1,r,mid+1,R,T);up(x);}double ask(int x,int l,int r,int L,int R){    if (l
        
         >1);    if (R<=mid) return ask(ls,l,mid,L,R);else    if (L>mid) return ask(rs,mid+1,r,L,R);else    return ask(ls,l,mid,L,mid)+ask(rs,mid+1,r,mid+1,R);}int main(){    freopen("exam.in","r",stdin);    freopen("exam.out","w",stdout);    scanf("%d%d",&n,&m);    for (int i=1;i<=n;i++) scanf("%lf",&p[i]);    Build(1,1,n);    while(m--){        int h,L,R;double T;scanf("%d%d%d",&h,&L,&R);        if (!h) printf("%.8lf\n",exp(-ask(1,1,n,L,R)));else scanf("%lf",&T),change(1,1,n,L,R,T);    }    return 0;}