P3772 [CTSC2017] 游戏
sol
首先，由期望的线性性，把贡献拆到单点上，对每一场计算其胜利的概率即可。
首先已知的局可以不管，未知的局，显然只与其两侧最近的已知局有关。后面运用的一些概率表达在题面最下面有提到，就不额外解释了。
记 \(L,R\) 分别为两侧已知局与已知状态相同的事件，\(X\) 表示当前局获胜的概率，那么我们就是要求：\(p(X\mid LR)\)。这个游戏是一个 Markov 过程，每个状态只依赖于上一个状态转移，则可以推出下式：
\[\begin{aligned}
p(X\mid LR)&=\frac{p(XLR)}{p(LR)}\\
&=\frac{p(L)p(X\mid L)p(R\mid X)}{p(L)p(R\mid L)}\\
&=\frac{p(X\mid L)p(R\mid X)}{p(R\mid L)}
\end{aligned}
\]
感性理解这个式子的话也是简单的，就是 \(L\) 必然发生时，\(XR\) 同时发生的概率比上 \(R\) 发生的概率，也就是要求的 \(X\) 发生的概率。
这个东西已经可以求了，考虑优化，上面说到每个局只与相邻两个已知局有关，那么考虑对一个未知局连续段统一计算。
分母是易求的，只需要顺序递推一下即可，有转移方程：
\[f(i,1)=p_if(i-1,1)+q_if(i-1,0)\\
f(i,0)=(1-p_i)f(i-1,1)+(1-q_i)f(i-1,0)
\]
状态设计显然。考虑分子，也就是钦定 \(x\) 处必胜，并对所有情况求和。这个直接状态设计的话有点复杂，这里就略去了，因为后面介绍的转移方式很方便。
那么考虑 set 维护所有已知点，更新时动态计算变化的连续段答案，利用矩阵把转移挂到线段树上区间求和即可。
设计状态矩阵，两个事件分别表示当前赢和输：
\[\begin{bmatrix}
p(W)&p(L)
\end{bmatrix}
\]
\(f\) 的转移矩阵设计直接照搬即可：
\[\begin{bmatrix}
p_i&(1-p_i)\\
q_i&(1-q_i)
\end{bmatrix}
\]
考虑分子，钦定一个点必胜是简单的，把那个位置的转移矩阵改成下面这个样子即可：
\[\begin{bmatrix}
p_i&0\\
q_i&0
\end{bmatrix}
\]
在线段树上维护钦定一个点的所有情况求和是简单的，每个节点额外维护一个矩阵信息 \(G\) 表示区间已有一个钦定点的状态，记当前节点为 \(x\)，两个子儿子分别为 \(ls\) 和 \(rs\)，区间转移矩阵信息记作 \(F\)，有转移：
\[G_x=G_{ls}F_{rs}+F_{ls}G_{rs}
\]
意义显然。
具体实现细节的话，可以考虑钦定 \(0,n+1\) 必胜来方便代码，其余的就参照代码实现吧。
code
const int N=2e5+5;struct Mat{flt dat[2][2];Mat(){rep(i,0,1)rep(j,0,1)dat[i][j]=0;}Mat(flt a,flt b,flt c,flt d){dat[0][0]=a,dat[0][1]=b,dat[1][0]=c,dat[1][1]=d;}inline flt* operator[](int k){return dat[k];}friend inline Mat operator*(Mat a,Mat b){Mat c;rep(i,0,1)rep(j,0,1)rep(k,0,1)c[i][j]+=a[i][k]*b[k][j];return c;}friend inline Mat operator+(Mat a,Mat b){Mat c;rep(i,0,1)rep(j,0,1)c[i][j]=a[i][j]+b[i][j];return c;}
};int n,m;
flt p[N],q[N];
set<int> st;
bool w[N];
int ck;flt cn;Mat M[N],dat[N<<2],pro[N<<2];
void build(int x=1,int l=1,int r=n){if(l==r){dat[x]=M[l]={p[l],1-p[l],q[l],1-q[l]};pro[x]={p[l],0,q[l],0};return;}int m=l+r>>1;build(x<<1,l,m);build(x<<1|1,m+1,r);dat[x]=dat[x<<1]*dat[x<<1|1];pro[x]=pro[x<<1]*dat[x<<1|1]+dat[x<<1]*pro[x<<1|1];
}
pair<Mat,Mat> query(int lq,int rq,int x=1,int l=1,int r=n){if(lq<=l&&r<=rq)return {dat[x],pro[x]};int m=l+r>>1;if(rq<=m)return query(lq,rq,x<<1,l,m);if(m<lq)return query(lq,rq,x<<1|1,m+1,r);auto resl=query(lq,rq,x<<1,l,m),resr=query(lq,rq,x<<1|1,m+1,r);return {resl.fir*resr.fir,resl.sec*resr.fir+resl.fir*resr.sec};
}
inline flt calc(int l,int r){if(l==r-1)return 0;Mat m;m[0][w[l]^1]=1;auto res=query(l+1,r-1);Mat sum=m*res.fir*M[r],prd=m*res.sec*M[r];return prd[0][w[r]^1]/sum[0][w[r]^1];
}inline void Main(){char type;cin>>n>>m>>type;cin>>p[1];rep(i,2,n)cin>>p[i]>>q[i];st.insert(0),st.insert(n+1);build();M[n+1]={1,0,1,0};w[0]=w[n+1]=1;cn=calc(0,n+1);rep(i,1,m){string op;cin>>op;if(op=="add"){int x,c;cin>>x>>c;if(w[x]=c)++ck;auto it=st.lower_bound(x);int r=*it;int l=*--it;cn+=calc(l,x)+calc(x,r)-calc(l,r);st.insert(x);}else{int x;cin>>x;if(w[x])--ck;auto it=st.upper_bound(x);int r=*it;int l=*----it;cn+=calc(l,r)-calc(l,x)-calc(x,r);st.erase(x);}put(ck+cn);}
}