题目描述

略

Sol

显然不能直接暴力模拟。

观察这个东西本质在干什么，就是某一次操作可能进行可能不进行，然后求所有情况下被标记节点总数。

这个显然可以转化为概率问题，每次有二分之一的概率进行，问最后期望多少个节点被标记。

只需要最后把答案乘上 \(2^t\) ， \(t\) 为操作次数就行了。

所以我们只需要求出一个点有标记的概率，这个似乎可以一次次递推得到。

于是我们讨论一些情况。容易发现一个点被标记只可能是直接被标记或是标记下放下来，于是我们只需要设 \(P[u]\) 表示 \(u\)点被标记的概率，设 \(Q[u]\) 表示这个节点到根的所有节点中至少有一个被标记的概率。

然后对于一次修改分情况讨论。

修改覆盖了一条祖先链但没有到达当前节点 \(P\rightarrow P,Q\rightarrow 0.5Q+0.5\)
修改直接覆盖当前点 \(P\rightarrow 0.5P+0.5,Q\rightarrow 0.5Q+0.5\)
修改经过当前点往下 \(P\rightarrow 0.5P,Q\rightarrow 0.5Q\)
修改在父亲处往其他方向走 \(P\rightarrow 0.5P+0.5Q,Q\rightarrow Q\)
修改在父亲上方就往其他方向走了 \(P\rightarrow P,Q\rightarrow Q\)

然后直接线段树就行了，另外维护一个 \(P\) 的和就可以算答案了。

code:

#include<bits/stdc++.h>

#define Set(a,b) memset(a,b,sizeof(a))

using namespace std;

const int N=1e5+10;

const int mod=998244353;

const int inv2=(mod+1)/2;

template <typename T> inline void init(T&x){

	x=0;char ch=getchar();bool t=0;

	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;

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

	if(t) x=-x;return;

}

typedef long long ll;

template<typename T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}

template<typename T>inline void Dec(T&x,int y){x-=y;if(x <  0) x+=mod;return;}

template<typename T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}

inline int Sum(int x,int y){x+=y;if(x>=mod) return x-mod;return x;}

inline int Dif(int x,int y){x-=y;if(x < 0 ) return x+mod;return x;}

int n,m;

int P[N<<2],Q[N<<2],S[N<<3];

struct tag{

	int mul,add;

	tag(int _mul=1,int _add=0){mul=_mul,add=_add;}

	inline bool pd(){return (mul!=1)||add;}

	inline int F(int x){return ((ll)mul*x+add)%mod;}

}Tag[N<<2];

inline tag Merge(tag A,tag B){

	int mul=(ll)A.mul*B.mul%mod;

	int add=((ll)B.mul*A.add+B.add)%mod;

	return tag(mul,add);

}

#define ls (u<<1)

#define rs (u<<1|1)

inline void update(int u){S[u]=Sum(Sum(S[ls],S[rs]),P[u]);return;}

inline void Upd(int u){P[u]=Sum((ll)P[u]*inv2%mod,(ll)Q[u]*inv2%mod);update(u);return;}

inline void Push(int u,tag T){Q[u]=T.F(Q[u]);Tag[u]=Merge(Tag[u],T);return;}

inline void push_down(int u){if(Tag[u].pd()){Push(ls,Tag[u]);Push(rs,Tag[u]);Tag[u]=tag();}return;}

void Modify(int u,int l,int r,int L,int R){

	if(l>=L&&r<=R) {// 当前节点为标记自己 , 下面的是覆盖父亲

		tag T=tag(inv2,inv2);Dec(S[u],P[u]);

		P[u]=T.F(P[u]),Q[u]=T.F(Q[u]);

		Inc(S[u],P[u]);Tag[u]=Merge(Tag[u],T);

		return;

	}push_down(u);int mid=(l+r)>>1;

	P[u]=(ll)P[u]*inv2%mod,Q[u]=(ll)Q[u]*inv2%mod;// 经过自己

	if(mid>=R) Modify(ls,l,mid,L,R),Upd(rs);//经过一边

	else if(mid<L) Modify(rs,mid+1,r,L,R),Upd(ls);

	else Modify(ls,l,mid,L,mid),Modify(rs,mid+1,r,mid+1,R);

	update(u);

}

int main()

{

	init(n),init(m);int base=1;

	for(int i=1;i<=m;++i) {

		int l,r;int op;init(op);

		if(op==2) printf("%lld\n",(ll)base*S[1]%mod);

		else {Inc(base,base);init(l),init(r);Modify(1,1,n,l,r);}

	}

	return 0;

}

rightarrow

【LuoguP5280】[ZJOI2019] 线段树

题目描述

Sol