题解 P3772 【[CTSC2017]游戏】

· · 题解

前置知识：贝叶斯公式

设 A,B 是两个随机事件。定义 P(A|B) 为在 B 事件发生的情况下 A 发生的概率。显然有

P(A|B)=\dfrac{P(AB)}{P(B)}

同样

P(B|A)=\dfrac{P(AB)}{P(A)}

则

P(A|B)=\dfrac{P(B|A)\times P(A)}{P(B)}

根据期望的线性性，我们可以单独计算每个未知的局面的获胜概率。设 x 是一个未知局面，显然 x 获胜的概率只与 x 左边的第一个已知局面 l 和右边的第一个已知局面 r 有关。记事件 X 为小 P 在第 x 局中获胜，事件 L,R 为第 l,r 获胜者和已知相符。则欲求为

P(X|L,R)=\dfrac{P(L,R|X)\times P(X)}{P(L,R)} =\dfrac{P(L|X)P(R|X)P(X)}{P(L,R)} =\dfrac{P(L|X)P(R|X)P(X)}{P(R|L)P(L)} =\dfrac{P(X|L)P(R|X)}{P(R|L)}

此时分母是一个定值，在求和的时候可以提出维护。换句话说，

\sum_{l < x <r}\dfrac{P(X|L)P(R|X)}{P(R|L)}=\dfrac{\sum_{l < x <r}P(X|L)P(R|X)}{P(R|L)}

分母可以用线段树维护矩阵乘法预处理出——对于每个点维护一个 2\times 2 矩阵 F_i，F(0,0)=1-q_i,F(0,1)=q_i,F(1,0)=1-p_i,F(1,1)=p_i。容易验证 这样乘起来符合组合意义。

至于分子，P(X|L)P(R|X) 可以理解为从 l 到 r 进行矩阵乘法时，在 x 处只乘 F_x 中第二维为 1 的元素。换言之构造另一个矩阵 G_x，G(0,0)=G(1,0)=0，要求则变成 \sum_{x=l}^rF_l\times F_{l+1}\times \cdots\times F_{x-1}\times G_x\times \cdots\times F_r。这个也可以在线段树上维护，每次维护一个区间的 G 矩阵，对于每个节点 k，有

G_k=G_{l(k)}\times F_{r(k)}+F_{l(k)}\times F_{r(k)}

（l(k),r(k) 分别代表 k 的左右子节点）

这样就大致解决了这道题。关于实现细节，可以开一个 set 维护所有已知的位置。

代码：

#include<cstdio>
#include<set>

using namespace std;

double p[300000],q[300000];

struct mat
{
    int r,c;double val[2][2];
    double* operator[](int x){return val[x];}
    const double* operator[](int x)const{return val[x];}
    mat(int rr=2,int cc=2):r(rr),c(cc){for(int i=0;i<2;i++)for(int j=0;j<2;j++)val[i][j]=0;} 
};
mat operator+(mat a,mat b){for(int i=0;i<a.r;i++)for(int j=0;j<a.c;j++)a[i][j]+=b[i][j];return a;}
mat operator*(mat a,mat b)
{
    mat c(a.r,b.c);
    for(int i=0;i<a.r;i++)
    {
        for(int j=0;j<b.c;j++)
        {
            for(int k=0;k<a.c;k++)
            {
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    return c; 
}

struct dat
{
    mat sum,pri;
};
dat operator*(const dat& a,const dat& b)
{
    dat c;c.pri=a.pri*b.pri,c.sum=a.sum*b.pri+a.pri*b.sum;return c;
}
struct SegmentTree
{
    struct nd
    {
        int l,r;dat x;
    }t[800000];
    void build(int l,int r,int k=1)
    {
        t[k].l=l,t[k].r=r;
        if(l==r)
        {
            t[k].x.pri[1][1]=p[l],t[k].x.pri[1][0]=1-p[l],
            t[k].x.pri[0][1]=q[l],t[k].x.pri[0][0]=1-q[l];
            t[k].x.sum[1][1]=p[l],t[k].x.sum[0][1]=q[l];
            return;
        }
        int mid=(l+r)>>1;build(l,mid,k<<1),build(mid+1,r,k<<1|1);
        t[k].x=t[k<<1].x*t[k<<1|1].x;
    }
    dat query(int l,int r,int k=1)
    {
        if(l<=t[k].l&&t[k].r<=r)return t[k].x;
        int mid=(t[k].l+t[k].r)>>1;
        if(r<=mid)return query(l,r,k<<1);
        if(l>mid)return query(l,r,k<<1|1);
        return query(l,r,k<<1)*query(l,r,k<<1|1);
    }
    void output(int k)
    {
        printf("%d: %d %d\n",k,t[k].l,t[k].r);
        for(int i=0;i<2;i++)for(int j=0;j<2;j++)printf("%.2lf ",t[k].x.pri[i][j]);puts("");
        if(t[k].l==t[k].r)return;output(k<<1);output(k<<1|1);
    }
}T;

int a[300000];

double calc(int l,int r)
{
    dat x=T.query(l+1,r);return x.sum[a[l]][a[r]]/x.pri[a[l]][a[r]];
}

set<int> st;char op[10];

int main()
{
    //mat A,B;A[0][0]=1,A[1][1]=2,B[1][0]=B[1][1]=1;A=A*B;for(int i=0;i<2;i++)for(int j=0;j<2;j++)printf("%lf ",A[i][j]);puts("");
    int n=0,m=0;scanf("%d%d%*s",&n,&m);
    scanf("%lf",&p[1]);for(int i=2;i<=n;i++)scanf("%lf%lf",&p[i],&q[i]);
    p[0]=1,q[0]=1;a[0]=1,a[n+1]=0;st.insert(0),st.insert(n+1);
    T.build(0,n+1);//T.output(1);
    double ans=calc(0,n+1);//printf("%lf\n",ans);
    while(m--)
    {
        scanf("%s",op);
        if(op[0]=='a')
        {
            int pos=0;scanf("%d",&pos);scanf("%d",&a[pos]);
            set<int>::iterator it=st.lower_bound(pos);int r=*it;it--;int l=*it;
            ans-=calc(l,r);ans+=calc(l,pos),ans+=calc(pos,r);
            st.insert(pos);
        }
        else
        {
            int pos=0;scanf("%d",&pos);st.erase(pos);
            set<int>::iterator it=st.lower_bound(pos);int r=*it;it--;int l=*it;
            ans+=calc(l,r);ans-=calc(l,pos),ans-=calc(pos,r);
        }
        printf("%.6lf\n",ans);
    }
    return 0;
}