Codeforces712E

传送门 here

题意：

有n个赌场，第i个赌场的胜率为$ P_i$，在第i个赌场若取胜则到达第$ i+1$个赌场，反之到达第$ i-1$个赌场

定义统治赌场$ L...R$为从赌场$ L$开始，从赌场$ R+1$结束且期间没有到达过$ L$前面的赌场(没有在赌场$ L$输过)

有$ q$次操作，修改一个赌场的胜率或者询问统治赌场$ L...R$的概率

这题真的很妙啊...

我们定义$ f(i)$为从i走到目标地点的概率

显然当询问$ L...R$时有$ f(L-1)=0,f(R+1)=1$

根据题意有$ f(i)=P_if(i+1)+(1-P_i)f(i-1)$

移项得$ f(i)-f(i-1)=P_if(i+1)+(1-1-P_i)f(i-1)=P_i(f(i+1)-f(i-1))$

定义$ g(i)=f(i)-f(i-1)$

则有$ g(i)=P_i(f(i+1)-f(i-1))$

容易发现$ g(L)=f(L)$也就是所要求的答案

计算$ g(i+1)+g(i)=f(i+1)-f(i)+f(i)-f(i-1)=f(i+1)-f(i-1)=\frac{1}{P_i}g(i)$

因而有$ g(i+1)=\frac{1-P_i}{P_i}g(i)$

根据g的定义有$ \sum\limits_{i=L}^Rg(i)=f(R+1)-f(L-1)=1$

我们又知道$ g(i+1)$和$ g(i)$的比值关系，设为$ t_i$

则有$ g(L)*(1+t_L+t_Lt_{L+1}+...+t_{L}*...*t_{R})=1$

就可以用线段树维护t的信息计算结果了

由于只需要四位精度，因此当括号内的数超过$ 10000$即可跳出避免爆double

my code:

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define rt register int

#define ll long long

#define r read()

using namespace std;

ll read()

{

    ll x = ; int zf = ; char ch;

    while (ch != '-' && (ch < '' || ch > '')) ch = getchar();

    if (ch == '-') zf = -, ch = getchar();

    while (ch >= '' && ch <= '') x = x *  + ch - '', ch = getchar(); return x * zf;

}

int i,j,k,m,n,x,y,z,cnt,all,num;

double p[],val[],qz[];

struct segment_tree{

    int L,R;double val,ji;

}a[];

void build(const int x,const int L,const int R)

{

    a[x].L=L;a[x].R=R;

    if(L==R)

    {

        a[x].val=a[x].ji=val[L];

        return;

    }

    const int mid=L+R>>;

    build(x<<,L,mid);build(x<<|,mid+,R);

    a[x].val=a[x<<].val+a[x<<|].val*a[x<<].ji;

    a[x].ji=a[x<<].ji*a[x<<|].ji;

}

void change(const int x,const int L,const double val)

{

    if(a[x].L==a[x].R)

    {

        a[x].val=a[x].ji=val;

        return;

    }

    L<=a[x].L+a[x].R>>?change(x<<,L,val):change(x<<|,L,val);

    a[x].val=a[x<<].val+a[x<<|].val*a[x<<].ji;

    a[x].ji=a[x<<].ji*a[x<<|].ji;

}

double ansa,ansb;

void query(const int x,const int L,const int R)

{

    if(ansa>)return;

    if(a[x].L>R||a[x].R<L)return;

    if(a[x].L>=L&&a[x].R<=R)

    {

        ansa+=a[x].val*ansb;

        ansb*=a[x].ji;

        return;

    }

    query(x<<,L,R);query(x<<|,L,R);

}

int main()

{

    n=r;m=r;

    for(rt i=;i<=n;i++)

    {

        x=r;y=r;

        p[i]=(double)x/(double)y;

        val[i]=(-p[i])/p[i];

    }

    build(,,n);

    while(m--)

    {

        int opt=r;

        if(opt==)

        {

            int L=r,R=r;ansa=;ansb=;query(,L,R);

            printf("%.6f\n",/(ansa+));

        }

        else

        {

            int L=r;x=r;y=r;

            double t=(double)x/(double)y;

            change(,L,(-t)/t);

            p[L]=t;

        }

    }

    return ;

}

巴特西

Codeforces712E

最新文章

热门文章