题解：P3772 [CTSC2017] 游戏
LastKismet
·
·
题解
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}
$$
\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
```cpp
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);
}
}
```