传送门

• 考虑 $i$ 为 1 的概率更前后第一个确定的游戏有关，即 $i$ 为 1 的概率为
  $P(x_i=1|x_l=a,x_r=b)=\frac{P(x_i=1,x_l=a,x_r=b)}{P(x_l=a,x_r=b)}\\=\frac{P(x_i=1,x_r=b|x_l=a)P(x_l=a)}{P(x_r=b|x_l=a)P(x_l=a)}\\=\frac{P(x_i=1,x_r=b|x_l=a)}{P(x_r=b|x_l=a)}$
  用线段树维护矩阵即可

#include<bits/stdc++.h>
#define cs const
using namespace std;
typedef double db;
cs int N = 2e5 + 50;
int n, m, S[N];
db p[N], q[N];
struct mat{db a[2][2];mat(){ a[0][0]=a[0][1]=a[1][0]=a[1][1]=0; }mat operator * (cs mat &A){mat B; for(int i=0; i<2; i++)for(int j=0; j<2; j++) for(int k=0; k<2; k++)B.a[i][j]+=a[i][k]*A.a[k][j]; return B;}mat operator + (cs mat &A){mat B; for(int i=0; i<2; i++)for(int j=0; j<2; j++) B.a[i][j]=a[i][j]+A.a[i][j];return B;}
};
struct node{ mat a, sm; };
node operator + (node a, node b){return (node){a.a * b.a, a.sm * b.a + a.a * b.sm};
}
namespace SGT{cs int N = ::N << 2;node vl[N];#define mid ((l+r)>>1)void pushup(int x){ vl[x]=vl[x<<1]+vl[x<<1|1]; }void build(int x, int l, int r){if(l==r){vl[x].a.a[0][0]=1-q[l];vl[x].a.a[0][1]=q[l];vl[x].a.a[1][0]=1-p[l];vl[x].a.a[1][1]=p[l];vl[x].sm.a[0][1]=q[l];vl[x].sm.a[1][1]=p[l];return;} build(x<<1,l,mid); build(x<<1|1,mid+1,r);pushup(x);}node query(int x, int l, int r, int L, int R){if(L<=l&&r<=R) return vl[x]; if(R<=mid) return query(x<<1,l,mid,L,R);if(L>mid) return query(x<<1|1,mid+1,r,L,R);return query(x<<1,l,mid,L,R)+query(x<<1|1,mid+1,r,L,R);}
}
set<int> G;
int pre(int x){ if(G.empty()) return 0;auto c=G.lower_bound(x); return c==G.begin()?0:*(--c); 
}
int suf(int x){ if(G.empty()) return n+1;auto c=G.upper_bound(x); return c==G.end()?n+1:*c;
}
db ans;
db upt(int l, int r){node vl=SGT::query(1,0,n+1,l+1,r);return vl.sm.a[S[l]][S[r]] / vl.a.a[S[l]][S[r]];
}
void Add(){int x, c; scanf("%d%d",&x,&c); S[x]=c;int l=pre(x), r=suf(x); G.insert(x); ans-=upt(l,r); ans+=upt(l,x); ans+=upt(x,r);
}
void Del(){int x; scanf("%d",&x);int l=pre(x), r=suf(x); ans-=upt(l,x); ans-=upt(x,r); ans+=upt(l,r); G.erase(x);
}
int main(){#ifdef FSYolandafreopen("1.in","r",stdin);#endifchar opt[5];scanf("%d%d%s",&n,&m,opt); scanf("%lf",&p[1]);for(int i=2; i<=n; i++) scanf("%lf%lf",&p[i],&q[i]);p[0]=q[0]=1; S[0]=1; S[n+1]=0; SGT::build(1,0,n+1);ans+=upt(0,n+1);while(m--){scanf("%s",opt);if(opt[0]=='a') Add();if(opt[0]=='d') Del(); printf("%.4lf\n",ans);} return 0;
}