「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;
}