\(\mathscr{Description}\)
有 \(n\) 个随机真值 \(x_{1..n}\), 已知 \(P(x_1=1)=p_1\), 对于 \(2\le i\le n\), \(P(x_i=1\mid x_{i-1}=1)=p_i\), \(P(x_i=1\mid x_{i-1}=0)=q_i\). 设事件集合 \(S\), 初始时 \(S=\varnothing\). 给出 \(m\) 次修改, 每次修改:
- 给定 \(i,c\), 令 \(S\gets S\cup\{x_i=c\}\).
- 给定 \(i\), 令 \(S\gets S\setminus\{x_i=\star\}\).
每次修改完成后, 求出 \(E\left(\sum_{i=1}^nx_i\mid S\right)\), 保留浮点.
\(\mathscr{Solution}\)
令 \(\xi:\{x_{1..n}\}\mapsto\sum_{i=1}^nx_i\), 那么
\[\begin{aligned} E(\xi\mid S) &= \sum_iiP(\xi=i\mid S)\\ &= \sum_iiP(\xi=i\land S)/P(S)\\ &=E([S]\times\xi)/P(S), \end{aligned} \]其中当 \(S\) 内事件全部发生时 \([S]=1\), 否则 \([S]=0\).
现在, 我们的任务变成了维护出 \(E([S]\times\xi)\) 和 \(P(S)\). 容易发现从 \(i-1\) 的信息推到 \(i\) 的信息是一个线性变换, 我们需要的东西大概有: \(P(x_i=1\land S)\), \(P(x_i=0\land S)\), \(E([S\land x_i=1]\times\xi_i)\) 和 \(E([S\land x_i=0]\times\xi_i)\), 其中 \(\xi_i:\{x_{1..i}\}\mapsto\sum_{j=1}^ix_j\), 然后按照规则变换一下:
\[\begin{bmatrix} P(x_i=1\land S)\\ P(x_i=0\land S)\\ E([S\land x_i=1]\xi_i)\\ E([S\land x_i=0]\xi_i) \end{bmatrix} = \begin{bmatrix} \color{red}{p_i} & \color{red}{q_i}\\ \color{blue}{1-p_i} & \color{blue}{1-q_i}\\ \color{red}{p_i} & \color{red}{q_i} & \color{red}{p_i} & \color{red}{q_i}\\ & & \color{blue}{1-p_i} & \color{blue}{1-q_i} & \end{bmatrix} \begin{bmatrix} P(x_{i-1}=1\land S)\\ P(x_{i-1}=0\land S)\\ E([S\land x_{i-1}=1]\xi_{i-1})\\ E([S\land x_{i-1}=0]\xi_{i-1}) \end{bmatrix}. \]中间的转移矩阵是 \(\{x_i=\star\}\notin S\) 的情况; 当 \(\{x_i=1/0\}\in S\) 时, 只需要对应保留矩阵中红色行和蓝色行即可, 其组合意义也比较简单.
最后, 钦定 \(x_0=1\), 将 \(\begin{bmatrix}1 & 0 & 0 & 0\end{bmatrix}^T\) 输入线性变换, 就能得到最终答案. 线段树维护矩阵, 复杂度 \(4^3\times \mathcal O(n\log n)\). 常数好像 ... 有点大欸.
\(\mathscr{Code}\)
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
#define double long double
const int MAXN = 2e5;
int n, m;
double p[MAXN + 5], q[MAXN + 5];
struct Matrix {
double mat[4][4];
// Matrix(): mat{} {}
inline double* operator [] (const int k) { return mat[k]; }
inline Matrix operator * (const Matrix& u) const {
Matrix ret; memset(ret.mat, 0, sizeof ret.mat);
rep (i, 0, 3) rep (k, 0, 3) rep (j, 0, 3) {
ret[i][j] += mat[i][k] * u.mat[k][j];
}
return ret;
}
};
#define unknown(i) Matrix{{ \
{ p[i], q[i] }, \
{ 1 - p[i], 1 - q[i] }, \
{ p[i], q[i], p[i], q[i] }, \
{ 0, 0, 1 - p[i], 1 - q[i] } \
}}
#define winR(i) Matrix{{ \
{ p[i], q[i] }, \
{}, \
{ p[i], q[i], p[i], q[i] }, \
{} \
}}
#define winB(i) Matrix{{ \
{}, \
{ 1 - p[i], 1 - q[i] }, \
{}, \
{ 0, 0, 1 - p[i], 1 - q[i] } \
}}
struct SegmentTree {
Matrix uni[MAXN << 2];
inline void pushup(const int u) {
uni[u] = uni[u << 1 | 1] * uni[u << 1];
}
inline void build(const int u, const int l, const int r) {
if (l == r) return void(uni[u] = unknown(l));
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
inline void modify(const int u, const int l, const int r,
const int x, const Matrix k) {
if (l == r) return void(uni[u] = k);
int mid = l + r >> 1;
if (x <= mid) modify(u << 1, l, mid, x, k);
else modify(u << 1 | 1, mid + 1, r, x, k);
pushup(u);
}
} sgt;
int main() {
scanf("%d %d %*s %Lf", &n, &m, &p[1]);
rep (i, 2, n) scanf("%Lf %Lf", &p[i], &q[i]);
sgt.build(1, 1, n);
while (m--) {
char op[10]; int i, c;
scanf("%s", op);
if (op[0] == 'a') {
scanf("%d %d", &i, &c);
sgt.modify(1, 1, n, i, c ? winR(i) : winB(i));
} else {
scanf("%d", &i);
sgt.modify(1, 1, n, i, unknown(i));
}
auto& ans = sgt.uni[1];
printf("%.12Lf\n", (ans[2][0] + ans[3][0]) / (ans[0][0] + ans[1][0]));
}
return 0;
}