自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

搬运于2025-08-24 21:52:32，当前版本为作者最后更新于2020-08-14 17:39:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：贝叶斯公式

设 $A,B$ 是两个随机事件。定义 $P(A|B)$ 为在 $B$ 事件发生的情况下 $A$ 发生的概率。显然有

$P(A|B)=\dfrac{P(AB)}{P(B)}$

同样

$P(B|A)=\dfrac{P(AB)}{P(A)}$

则

$P(A|B)=\dfrac{P(B|A)\times P(A)}{P(B)}$

根据期望的线性性，我们可以单独计算每个未知的局面的获胜概率。设 $x$ 是一个未知局面，显然 $x$ 获胜的概率只与 $x$ 左边的第一个已知局面 $l$ 和右边的第一个已知局面 $r$ 有关。记事件 $X$ 为小 P 在第 $x$ 局中获胜，事件 $L,R$ 为第 $l,r$ 获胜者和已知相符。则欲求为

$P(X|L,R)=\dfrac{P(L,R|X)\times P(X)}{P(L,R)}$

$=\dfrac{P(L|X)P(R|X)P(X)}{P(L,R)}$

$=\dfrac{P(L|X)P(R|X)P(X)}{P(R|L)P(L)}$

$=\dfrac{P(X|L)P(R|X)}{P(R|L)}$

此时分母是一个定值，在求和的时候可以提出维护。换句话说，

$\sum_{l < x <r}\dfrac{P(X|L)P(R|X)}{P(R|L)}=\dfrac{\sum_{l < x <r}P(X|L)P(R|X)}{P(R|L)}$

分母可以用线段树维护矩阵乘法预处理出——对于每个点维护一个 $2\times 2$ 矩阵 $F_i$，$F(0,0)=1-q_i,F(0,1)=q_i,F(1,0)=1-p_i,F(1,1)=p_i$。容易验证 这样乘起来符合组合意义。

至于分子，$P(X|L)P(R|X)$ 可以理解为从 $l$ 到 $r$ 进行矩阵乘法时，在 $x$ 处只乘 $F_x$ 中第二维为 $1$ 的元素。换言之构造另一个矩阵 $G_x$，$G(0,0)=G(1,0)=0$，要求则变成 $\sum_{x=l}^rF_l\times F_{l+1}\times \cdots\times F_{x-1}\times G_x\times \cdots\times F_r$。这个也可以在线段树上维护，每次维护一个区间的 $G$ 矩阵，对于每个节点 $k$，有

$G_k=G_{l(k)}\times F_{r(k)}+F_{l(k)}\times F_{r(k)}$

（$l(k),r(k)$ 分别代表 $k$ 的左右子节点）

这样就大致解决了这道题。关于实现细节，可以开一个 set 维护所有已知的位置。

代码：

#include<cstdio>
#include<set>

using namespace std;

double p[300000],q[300000];

struct mat
{
	int r,c;double val[2][2];
	double* operator[](int x){return val[x];}
	const double* operator[](int x)const{return val[x];}
	mat(int rr=2,int cc=2):r(rr),c(cc){for(int i=0;i<2;i++)for(int j=0;j<2;j++)val[i][j]=0;} 
};
mat operator+(mat a,mat b){for(int i=0;i<a.r;i++)for(int j=0;j<a.c;j++)a[i][j]+=b[i][j];return a;}
mat operator*(mat a,mat b)
{
	mat c(a.r,b.c);
	for(int i=0;i<a.r;i++)
	{
		for(int j=0;j<b.c;j++)
		{
			for(int k=0;k<a.c;k++)
			{
				c[i][j]+=a[i][k]*b[k][j];
			}
		}
	}
	return c; 
}

struct dat
{
	mat sum,pri;
};
dat operator*(const dat& a,const dat& b)
{
	dat c;c.pri=a.pri*b.pri,c.sum=a.sum*b.pri+a.pri*b.sum;return c;
}
struct SegmentTree
{
	struct nd
	{
		int l,r;dat x;
	}t[800000];
	void build(int l,int r,int k=1)
	{
		t[k].l=l,t[k].r=r;
		if(l==r)
		{
			t[k].x.pri[1][1]=p[l],t[k].x.pri[1][0]=1-p[l],
			t[k].x.pri[0][1]=q[l],t[k].x.pri[0][0]=1-q[l];
			t[k].x.sum[1][1]=p[l],t[k].x.sum[0][1]=q[l];
			return;
		}
		int mid=(l+r)>>1;build(l,mid,k<<1),build(mid+1,r,k<<1|1);
		t[k].x=t[k<<1].x*t[k<<1|1].x;
	}
	dat query(int l,int r,int k=1)
	{
		if(l<=t[k].l&&t[k].r<=r)return t[k].x;
		int mid=(t[k].l+t[k].r)>>1;
		if(r<=mid)return query(l,r,k<<1);
		if(l>mid)return query(l,r,k<<1|1);
		return query(l,r,k<<1)*query(l,r,k<<1|1);
	}
	void output(int k)
	{
		printf("%d: %d %d\n",k,t[k].l,t[k].r);
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)printf("%.2lf ",t[k].x.pri[i][j]);puts("");
		if(t[k].l==t[k].r)return;output(k<<1);output(k<<1|1);
	}
}T;

int a[300000];

double calc(int l,int r)
{
	dat x=T.query(l+1,r);return x.sum[a[l]][a[r]]/x.pri[a[l]][a[r]];
}

set<int> st;char op[10];

int main()
{
	//mat A,B;A[0][0]=1,A[1][1]=2,B[1][0]=B[1][1]=1;A=A*B;for(int i=0;i<2;i++)for(int j=0;j<2;j++)printf("%lf ",A[i][j]);puts("");
	int n=0,m=0;scanf("%d%d%*s",&n,&m);
	scanf("%lf",&p[1]);for(int i=2;i<=n;i++)scanf("%lf%lf",&p[i],&q[i]);
	p[0]=1,q[0]=1;a[0]=1,a[n+1]=0;st.insert(0),st.insert(n+1);
	T.build(0,n+1);//T.output(1);
	double ans=calc(0,n+1);//printf("%lf\n",ans);
	while(m--)
	{
		scanf("%s",op);
		if(op[0]=='a')
		{
			int pos=0;scanf("%d",&pos);scanf("%d",&a[pos]);
			set<int>::iterator it=st.lower_bound(pos);int r=*it;it--;int l=*it;
			ans-=calc(l,r);ans+=calc(l,pos),ans+=calc(pos,r);
			st.insert(pos);
		}
		else
		{
			int pos=0;scanf("%d",&pos);st.erase(pos);
			set<int>::iterator it=st.lower_bound(pos);int r=*it;it--;int l=*it;
			ans+=calc(l,r);ans-=calc(l,pos),ans-=calc(pos,r);
		}
		printf("%.6lf\n",ans);
	}
	return 0;
}