【loj2263】【CTSC2017】游戏

╰半橙微兮° 2021-12-23 01:41 185阅读 0赞

## 题目 ##

小\$R\$和小\$B\$一共完了\$n\$局游戏，第一局小\$R\$获胜的概率为\$p\_i\$，没有平局，对于第$ i $局游戏：

1.  如果第\$i-1\$局游戏小$ R \$获胜，那么第 局游戏小\$ R $获胜的概率为 \$p\_i\$，小$ B $获胜的概率为 \$1-p\_i\$
2.  如果第\$i-1\$局游戏小\$B\$获胜，那么第 局游戏小$ R $获胜的概率为 \$q\_i\$，小$ B $获胜的概率为 \$1-q\_i\$

有\$m\$次两种操作:

1 \$add \\ i \\ c\$ 加入第\$i\$局比赛的结果；

２$del i $　忘记第\$i\$局比赛的结果；

输出每次比赛小\$R\$获胜局数的期望；

\$1 \\le n,m \\le 200000\$

## 题解 ##

*  根据期望的线性性考虑每一局获胜的概率，每一局获胜的概率只和相邻的两个确定的局面有关系;  
    \\\[ \\begin\{align\} &bayes公式:\\\\ P(A|B)P(B) &= P(A\\ \\cap B) \\Leftrightarrow P(A|B) = \\frac\{P(B|A)P(A)\}\{P(B)\} \\\\ &P(x\_i=1|x\_l=a,x\_r=b)(1\\lt i \\le r)\\\\ &=\\frac\{P(x\_i=1,x\_l=a,x\_r=b)\}\{P(x\_l=a,x\_r=b)\}\\\\ &=\\frac\{P(x\_i=1,x\_l=a,x\_r=b)\}\{P(x\_l=a)P(x\_r=b|x\_l=a)\}\\\\ &=\\frac\{P(x\_i=1,x\_r=b|x\_l=a)\}\{P(x\_r=b|x\_l=a)\}\\\\ \\end\{align\} \\\]
 *  把转移写成矩阵\$A\_i\$，注意到分母即\$(\\Pi\_\{i>l\}^\{r\}A\_i)\_\{a,b\}\$，是个定值
 *  分母求和即\$(\\sum\_\{i>l\}^\{r\} \\ \\Pi\_\{j \\gt l\}^\{j \\lt i\} A\_j \\times B\_i \\times \\Pi\_\{j \\gt i\}^\{j \\lt r\} A\_j)\_\{a,b\}\$，即将\$A\_i\$换成一个只允许转移到1的矩阵\$B\_i\$，可以用线段树维护
 *  插入和删除用\$set\$维护即可
    
        #include<bits/stdc++.h>
        #define ls (k<<1)
        #define rs (k<<1|1)
        #define ld double
        #define fi first
        #define se second
        #define ls (k<<1)
        #define rs (k<<1|1)
        using namespace std;
        const int N=200010;
        int n,m;
        char op[10];
        map<int,int>S;
        map<int,int>::iterator it,pre,nxt;
        ld p[N],q[N],ans;
        struct Mat{
          ld c[2][2];
          Mat operator +(const Mat&A)const{
              Mat re;
              for(int i=0;i<2;++i)
              for(int j=0;j<2;++j){
                  re.c[i][j]=c[i][j]+A.c[i][j];
              }
              return re;
          }
          Mat operator *(const Mat&A)const{
              Mat re;
              for(int i=0;i<2;++i)
              for(int j=0;j<2;++j){
                  re.c[i][j]=0;
                  for(int k=0;k<2;++k)re.c[i][j]+=c[i][k]*A.c[k][j];
              }
              return re;
          }
        };
        struct data{Mat mul,sum;}tr[N<<2];
        data operator +(data A,data B){
          data re;
          re.mul=A.mul*B.mul;
          re.sum=A.mul*B.sum+A.sum*B.mul;
          return re;
        }
        void build(int k,int l,int r){
          if(l==r){
              tr[k].mul.c[1][1]=p[l];
              tr[k].mul.c[1][0]=1-p[l];
              tr[k].mul.c[0][1]=q[l];
              tr[k].mul.c[0][0]=1-q[l];
              tr[k].sum.c[1][1]=p[l];
              tr[k].sum.c[0][1]=q[l];
              return;
          }
          int mid=(l+r)>>1;
          build(ls,l,mid);
          build(rs,mid+1,r);
          tr[k]=tr[ls]+tr[rs];
        }
        data query(int k,int l,int r,int x,int y){
          if(l==x&&r==y)return tr[k];
          int mid=(l+r)>>1;
          if(y<=mid)return query(ls,l,mid,x,y);
          else if(x>mid)return query(rs,mid+1,r,x,y);
          else return query(ls,l,mid,x,mid)+query(rs,mid+1,r,mid+1,y);
        }
        ld ask(int l,int r){
          data tmp=query(1,0,n+1,l+1,r);
          return tmp.sum.c[S[l]][S[r]]/tmp.mul.c[S[l]][S[r]];
        }
        int main(){
        //    freopen("game.in","r",stdin);
        //    freopen("game.out","w",stdout);
          scanf("%d%d%s%lf",&n,&m,op,&p[1]);
          for(int i=2;i<=n;++i)scanf("%lf%lf",&p[i],&q[i]);
          p[0]=q[0]=1;
          S[0]=1;S[n+1]=0;
          build(1,0,n+1);
          ans=ask(0,n+1);
          for(int i=1,x,y;i<=m;++i){
              scanf("%s%d",op,&x);
              if(op[0]=='a'){
                  scanf("%d",&y);S[x]=y;
                  it=S.lower_bound(x);
                  pre=it,--pre;nxt=it,++nxt;
                  ans-=ask((*pre).fi,(*nxt).fi);
                  ans+=ask((*pre).fi,(*it).fi);
                  ans+=ask((*it).fi,(*nxt).fi);
              }else{
                  it=S.lower_bound(x);
                  pre=it,--pre;nxt=it,++nxt;
                  ans-=ask((*pre).fi,(*it).fi);
                  ans-=ask((*it).fi,(*nxt).fi);
                  ans+=ask((*pre).fi,(*nxt).fi);
                  S.erase(it);
              }
              printf("%.10lf\n",ans);
          }
          return 0;
        }

转载于:https://www.cnblogs.com/Paul-Guderian/p/10826072.html