【LuoguP5280】[ZJOI2019] 線段樹

題目連結

題目描述

略

Sol

顯然不能直接暴力模拟。

觀察這個東西本質在幹什麼，就是某一次操作可能進行可能不進行，然後求所有情況下被标記節點總數。

這個顯然可以轉化為機率問題，每次有二分之一的機率進行，問最後期望多少個節點被标記。

隻需要最後把答案乘上 2 t 2^t 2t ， t t t 為操作次數就行了。

是以我們隻需要求出一個點有标記的機率，這個似乎可以一次次遞推得到。

于是我們讨論一些情況。容易發現一個點被标記隻可能是直接被标記或是标記下放下來，于是我們隻需要設 P [ u ] P[u] P[u] 表示 u u u點 被标記的機率，設 Q [ u ] Q[u] Q[u] 表示這個節點到根的所有節點中至少有一個被标記的機率。

然後對于一次修改分情況讨論。

1. 修改覆寫了一條祖先鍊但沒有到達目前節點 P → P , Q → 0.5 Q + 0.5 P\rightarrow P,Q\rightarrow 0.5Q+0.5 P→P,Q→0.5Q+0.5
2. 修改直接覆寫目前點 P → 0.5 P + 0.5 , Q → 0.5 Q + 0.5 P\rightarrow 0.5P+0.5,Q\rightarrow 0.5Q+0.5 P→0.5P+0.5,Q→0.5Q+0.5
3. 修改經過目前點往下 P → 0.5 P , Q → 0.5 Q P\rightarrow 0.5P,Q\rightarrow 0.5Q P→0.5P,Q→0.5Q
4. 修改在父親處往其他方向走 P → 0.5 P + 0.5 Q , Q → Q P\rightarrow 0.5P+0.5Q,Q\rightarrow Q P→0.5P+0.5Q,Q→Q
5. 修改在父親上方就往其他方向走了 P → P , Q → Q P\rightarrow P,Q\rightarrow Q P→P,Q→Q

然後直接線段樹就行了，另外維護一個 P P 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;
}