「UOJ 299」「CTSC2017」游戏

UOJ #299

题意

小 R 和小 B 玩了 $n$ 局游戏，第一局小 R 获胜的概率是 $p_1$，对于第 $i(1<i\le n)$ 局，若第 $i-1$ 局小 R 获胜，则小 R 获胜的概率为 $p_i$，否则为 $q_i$

现在已经知道了若干局的胜负情况，求小 R 获胜次数的期望，在 $m$ 次增加或删除已知条件后都输出答案

$n,m\le 2\times 10^5$

后面的游戏结果会影响前面的概率 = =

做法

钦定第 $0$ 局小 R 获胜，第 $n+1$ 局小 B 获胜

设第 $i$ 局的结果为 $x_i$：若 $x_i=1$ 则表示小 R 获胜，若 $x_i=0$ 则表示小 B 获胜

考虑在确定了一些位置的情况下求第 $k$ 个位置的概率

这只和 $k$ 两侧最近的确定的位置有关

形式化地，找到最大的 $l(l<k)$ 和最小的 $r(r\ge k)$，即 $P(x_k=1|x_l,x_r)$

而

$$
\begin{aligned}
P(x_k=1|x_l,x_r) = & \frac{P(x_k=1,x_l,x_r)}{P(x_l,x_r)} \
= & \frac{P(x_k=1,x_r|x_l)\times P(x_l)}{P(x_r|x_l)\times P(x_l)} \
= & \frac{P(x_k=1,x_r|x_l)}{P(x_r|x_l)}
\end{aligned}
$$

分母即确定了 $l$ 处的值 $x_l$ 后，$r$ 处的值为当前 $x_r$ 的概率，可以简单求得

分子部分即在上述条件中钦定 $x_k=1$ 后的概率

现在只有 $x_l$ 的条件，于是可以递推

注意在有中间钦定的情况下，小 R 和小 B 获胜的概率之和不一定为 $1$

记 $i$ 处小 R 获胜概率为 $f_i$，小 B 为 $g_i$

用矩阵转移即

$$
(f_{i-1},g_{i-1})
\begin{bmatrix}
p_i & 1-p_i \
q_i & 1-q_i
\end{bmatrix}

(f_i, g_i)
$$

若在 $k$ 处，由于钦定了 $x_k=1$

矩阵变成

$$
\begin{bmatrix}
p_i & 0 \
q_i & 0
\end{bmatrix}
$$

现在对于相邻两个的确定位置 $l,r$，计算 $(l,r]$ 这一段的答案，可以分治地维护一个区间的矩阵的积和钦定其中某个位置为 $1$ 的所有方案

每次修改会改变三个区间

复杂度 $\mathcal O(n+m\log n)$

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 200005;
int n, m;
bool f[N];
double ans, p[N], q[N];
set<int> g;
struct xxx{
	struct matrix{
		double a[2][2];
		inline matrix operator +(const matrix &rhs)const{
			matrix ans;
			for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) ans.a[i][j]=a[i][j]+rhs.a[i][j];
			return ans;
		}
		inline matrix operator *(const matrix &rhs)const{
			matrix ans;
			ans.a[0][0]=a[0][0]*rhs.a[0][0]+a[0][1]*rhs.a[1][0];
			ans.a[0][1]=a[0][0]*rhs.a[0][1]+a[0][1]*rhs.a[1][1];
			ans.a[1][0]=a[1][0]*rhs.a[0][0]+a[1][1]*rhs.a[1][0];
			ans.a[1][1]=a[1][0]*rhs.a[0][1]+a[1][1]*rhs.a[1][1];
			return ans;
		}
	} a, b;
	inline xxx operator *(const xxx &rhs)const{
		xxx ans;
		return ans.a=a*rhs.a, ans.b=a*rhs.b+b*rhs.a, ans;
	}
} s[N<<2];
void build(int l, int r, int t){
	if(l==r){
		s[t].a.a[0][0]=p[l], s[t].a.a[0][1]=1-p[l];
		s[t].a.a[1][0]=q[l], s[t].a.a[1][1]=1-q[l];
		s[t].b.a[0][0]=p[l], s[t].b.a[1][0]=q[l];
		return;
	}
	int mid=(l+r)>>1, k=t<<1;
	build(l, mid, k), build(mid+1, r, k|1), s[t]=s[k]*s[k|1];
}
xxx query(int l, int r, int t, int L, int R){
	if(L<=l && r<=R) return s[t];
	int mid=(l+r)>>1, k=t<<1;
	if(R<=mid) return query(l, mid, k, L, R);
	if(L>mid) return query(mid+1, r, k|1, L, R);
	return query(l, mid, k, L, R)*query(mid+1, r, k|1, L, R);
}
double solve(int l, int r){
	xxx a=query(1, n+1, 1, l+1, r);
	return a.b.a[f[l]^1][f[r]^1]/a.a.a[f[l]^1][f[r]^1];
}
int main() {
	scanf("%d%d", &n, &m);
	while(isspace(getchar()));
	scanf("%lf", p+1);
	for(int i=2; i<=n; ++i) scanf("%lf%lf", p+i, q+i);
	build(1, n+1, 1), f[0]=1, g.insert(0), g.insert(n+1), ans=solve(0, n+1);
	while(m--){
		int x, y, l, r;
		while(isspace(getchar()));
		if((getchar(), getchar())=='d'){
			scanf("%d%d", &x, &y), f[x]=y;
			auto it=g.upper_bound(x);
			r=*it, l=*--it, g.insert(x);
			ans+=solve(l, x)+solve(x, r)-solve(l, r);
		}
		else{
			scanf("%d", &x);
			auto it=g.find(x);
			g.erase(it++), r=*it, l=*--it;
			ans+=solve(l, r)-solve(l, x)-solve(x, r);
		}
		printf("%.6lf\n", ans);
	}
	return 0;
}