【LOJ3043】「ZJOI2019」线段树

问题可以转化为每次区间覆盖操作有 \(\frac{1}{2}\) 的概率进行，求标记和的期望。于是我们只要求出所有点有标记的概率即可。

我们设 \(f_i\) 表示节点 \(i\) 有标记的概率， \(g_i\) 表示节点 \(i\) 的祖先节点有标记的概率。如果一个节点未完全被包含，那么其未被包含的节点是否有标记取决于其祖先节点是否有标记，故要用来自祖先节点的信息来更新答案（设未包含的节点为 \(j\) ，那么 \(f_j \leftarrow \frac{f_j+g_j}{2}\) ）。如果一个节点被完全包含，那么 \(f_i \leftarrow \frac{f_i+1}{2}\) ，其所有子节点(包括自己) \(g_j \leftarrow \frac{g_j+1}{2}\) ；否则因为当前到达的区间标记已被下传，所以 \(f_i\leftarrow \frac{f_i}{2}, g_i\leftarrow \frac{g_i}{2}\) 。线段树维护 \(f_i,g_i\) ， \(g_i\) 的维护需要打标记。

#include<cstdio>

#include<cassert>

inline int gi()

{

	char c=getchar(); int x=0;

	for(;c<'0'||c>'9';c=getchar());

	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';

	return x;

}

const int N=2e5+5,Mod=998244353,inv=Mod+1>>1;

int n,m,f[N<<2],g[N<<2],sum[N<<2],tg1[N<<2],tg2[N<<2],fm=1;

#define lx (x<<1)

#define rx (x<<1|1)

#define mul(x,y) (1ll*(x)*(y)%Mod)

#define div2(x) (1ll*(x)*inv%Mod)

void pushdown(int x)

{

	if(tg1[x]==1&&tg2[x]==0) return ;

	tg1[lx]=mul(tg1[lx],tg1[x]),tg1[rx]=mul(tg1[rx],tg1[x]);

	tg2[lx]=(mul(tg2[lx],tg1[x])+tg2[x])%Mod;

	tg2[rx]=(mul(tg2[rx],tg1[x])+tg2[x])%Mod;

	g[lx]=(mul(g[lx],tg1[x])+tg2[x])%Mod;

	g[rx]=(mul(g[rx],tg1[x])+tg2[x])%Mod;

	tg1[x]=1,tg2[x]=0;

}

void solve(int x)

{

	f[x]=div2((f[x]+g[x])%Mod);

	sum[x]=((sum[lx]+sum[rx])%Mod+f[x])%Mod;

}

void update(int x, int l, int r, int sl, int sr)

{

	if(sl<=l&&r<=sr)

	{

		f[x]=div2(f[x]+1);

		g[x]=div2(g[x]+1);

		sum[x]=((sum[lx]+sum[rx])%Mod+f[x])%Mod;

		tg1[x]=div2(tg1[x])%Mod;

		tg2[x]=(div2(tg2[x])+inv)%Mod;

		return ;

	}

	pushdown(x);

	f[x]=div2(f[x]),g[x]=div2(g[x]);

	int mid=l+r>>1;

	if(sl>mid)

		update(rx,mid+1,r,sl,sr),solve(lx);

	else if(sr<=mid)

		update(lx,l,mid,sl,sr),solve(rx);

	else update(lx,l,mid,sl,sr),update(rx,mid+1,r,sl,sr);

	sum[x]=((sum[lx]+sum[rx])%Mod+f[x])%Mod;

}

int main()

{

	n=gi(),m=gi();

	for(int i=1;i<=(n<<2);++i) tg1[i]=1;

	while(m--)

	{

		int op=gi();

		if(op==2) printf("%d\n",1ll*fm*sum[1]%Mod);

		else

		{

			fm=2ll*fm%Mod;

			int l=gi(),r=gi();

			update(1,1,n,l,r);

		}

	}

}

巴特西

【LOJ3043】「ZJOI2019」线段树

最新文章

热门文章