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