0%

「UOJ 299」「CTSC2017」游戏

UOJ #299. 【CTSC2017】游戏

题意

小 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)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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;
}