Solution
其实问题在于当你确定了后面的一个数之后因为不独立，所以会影响前面的概率，所以这时候我们就需要贝叶斯公式去计算了。
因为我们最后需要算的是期望赢的次数，所以我们可以对于每一个局面去考虑赢的概率并加起来。对于 \(x\)，我们假设上一次和下一次确定的局面分别为 \(L,R\)，那么我们存在：
\[p(x|L,R)=\frac{p(L,R|x)p(x)}{p(L,R)} \]\[=\frac{p(L|x)p(R|x)p(x)}{p(L)p(R|L)} \]\[=\frac{p(x|L)p(R|x)}{p(R|L)} \]这个玩意成立的重要一点就是 \(p(L|x)\) 和 \(p(R|x)\) 是独立的。
然后我们考虑怎么维护，因为其实我们是求和，所以我们是需要对于每个 \((l,r)\) 求出：
\[\sum_{x>l}^{x<r} \frac{p(x|L)p(R|x)}{p(R|L)} \]我们设 \(F(x)\) 为第 \(x\) 位的转移矩阵（上一位到下一位转移的概率的矩阵），那么可以看出分母是 \(\prod_{x=L+1}^{R} F(x)\) （取其中相应位置）。
考虑如何求出分母，我们可以设 \(G(x)\) 表示仅转移到 \(1\) 的概率矩阵，可以发现相当于 \(\sum_{x=L+1}^{R-1} F(L)\times F(L+1)\times ...\times G(x)\times F(x+1)\times ...\times F(R)\)，你发现这个玩意其实也可以用线段树维护。
然后我们就可以用set+线段树求出答案了，复杂度 \(\Theta(n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXN 200005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}
template <typename T> inline void chkmin (T &a,T b){a = min (a,b);}
int n,m,a[MAXN];
struct Matrix{
double mat[2][2];
Matrix(){for (Int i = 0;i < 2;++ i) for (Int j = 0;j < 2;++ j) mat[i][j] = 0;}
double * operator [] (const int &key){return mat[key];}
Matrix operator * (const Matrix &p)const{
Matrix New;
for (Int i = 0;i < 2;++ i)
for (Int j = 0;j < 2;++ j)
for (Int k = 0;k < 2;++ k)
New[i][k] += mat[i][j] * p.mat[j][k];
return New;
}
Matrix operator + (const Matrix &p)const{
Matrix New;
for (Int i = 0;i < 2;++ i)
for (Int j = 0;j < 2;++ j)
New[i][j] = mat[i][j] + p.mat[i][j];
return New;
}
};
struct node{
Matrix F,G;
node operator * (const node &p)const{
return node{F * p.F,G * p.F + F * p.G};
}
};
double p[MAXN],q[MAXN];
struct Segment{
node Sum[MAXN << 2];
void build (int x,int l,int r){
if (l == r){
Sum[x].G[1][1] = p[l],Sum[x].G[0][1] = q[l];
Sum[x].F[0][0] = 1 - q[l],Sum[x].F[0][1] = q[l],
Sum[x].F[1][0] = 1 - p[l],Sum[x].F[1][1] = p[l];
return ;
}
int mid = l + r >> 1;
build (x << 1,l,mid),build (x << 1 | 1,mid + 1,r),Sum[x] = Sum[x << 1] * Sum[x << 1 | 1];
}
node query (int x,int l,int r,int ql,int qr){
if (l >= ql && r <= qr) return Sum[x];
int mid = l + r >> 1;
if (qr <= mid) return query (x << 1,l,mid,ql,qr);
else if (ql > mid) return query (x << 1 | 1,mid + 1,r,ql,qr);
else return query (x << 1,l,mid,ql,qr) * query (x << 1 | 1,mid + 1,r,ql,qr);
}
}tree;
double calc (int L,int R){
node it = tree.query (1,0,n + 1,L + 1,R);
return it.G[a[L]][a[R]] / it.F[a[L]][a[R]];
}
signed main(){
read (n,m);char st[10]={};scanf ("%s",st + 1),scanf ("%lf",&p[1]),p[0] = q[0] = a[0] = 1,a[n + 1] = 0;
for (Int i = 2;i <= n;++ i) scanf ("%lf%lf",&p[i],&q[i]);
tree.build (1,0,n + 1);set <int> S;S.insert (0),S.insert (n + 1);
double ans = calc (0,n + 1);
while (m --> 0){
char str[10] = {};scanf ("%s",str + 1);
if (str[1] == 'a'){
int x,c;read (x,c),a[x] = c;
auto IT = S.upper_bound (x),IT1 = IT;-- IT1;
int l = *IT1,r = *IT;
ans -= calc (l,r),ans += calc (l,x) + calc (x,r),S.insert (x);
}
else{
int x;read (x);
auto IT = S.upper_bound (x),IT1 = IT;-- IT1,-- IT1;
int l = *IT1,r = *IT;
ans -= calc (l,x) + calc (x,r),ans += calc (l,r),S.erase (S.find (x));
}
printf ("%.6f\n",ans);
}
return 0;
}