如题。
ABC332 F.
算是一种期望与概率线段树。
考虑 $X $ 有 \(\dfrac{1}{d}\) 的概率变成 \(Y\) 的 \(E(X).\)
古典概型，得到 \(E(x)=\dfrac{d-1}{d} X +\dfrac{Y}{d}.\)
分作两步：
-
\(x \rightarrow \dfrac{d-1}{d}x\)
-
\(x\rightarrow x+\dfrac{1}{d}Y\)
线段树维护就好了。
居然可以一发 \(AC.\) 看来我又变强了。
程式
#include <bits/stdc++.h>
#define int long long
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int p=998244353;
const int N=2e5+10;
int w[N],tree[N<<2],tag[N<<2],tag2[N<<2];
int n,m;
void push_down(int rt,int l,int r){
tree[rt]*=tag2[rt], tree[rt]+=(r-l+1)*tag[rt], tree[rt]%=p;
if(l!=r){
tag[ls]*=tag2[rt], tag[rs]*=tag2[rt];
tag2[ls]*=tag2[rt], tag2[rs]*=tag2[rt];
tag[ls]%=p, tag2[ls]%=p, tag[rs]%=p;tag2[rs]%=p;
}
if(l!=r)tag[ls]+=tag[rt],tag[rs]+=tag[rt],tag[ls]%=p,tag[rs]%=p;
tag[rt]=0;
tag2[rt]=1;
}
void push_up(int rt,int l,int r){
if(l!=r)push_down(lson),push_down(rson);
tree[rt]=tree[ls]+tree[rs];
}
void update(int rt,int l,int r,int L,int R,int k){
push_down(rt,l,r);
if(L<=l && r<=R){
tag[rt]+=k;
tag[rt]%=p;
return;
}
if(L<=mid)update(lson,L,R,k);
if(R>mid) update(rson,L,R,k);
push_up(rt,l,r);
}
void update2(int rt,int l,int r,int L,int R,int k){
push_down(rt,l,r);
if(L<=l && r<=R){
tag2[rt]*=k, tag[rt]*=k, tag[rt]%=p, tag2[rt]%=p;
return;
}
if(L<=mid)update2(lson,L,R,k);
if(R>mid) update2(rson,L,R,k);
push_up(rt,l,r);
}
int query(int rt,int l,int r,int L,int R){
push_down(rt,l,r);
if(L<=l&&r<=R)return tree[rt]%p;
int res=0;
if(L<=mid) res+=query(lson,L,R),res%=p;
if(R>mid) res+=query(rson,L,R),res%=p;
return res%p;
}
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p, b>>=1;
}
return res;
}
int inv(int x){ return qpow(x,p-2); }
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;++i){
int x; scanf("%lld",&x);
update(1,1,n,i,i,x);
}
while(m--){
int l,r,x;
scanf("%lld%lld%lld",&l,&r,&x);
int d=(r-l+1),iv=inv(d);
update2(1,1,n,l,r,(d-1)*iv);
update(1,1,n,l,r,iv*x);
}
for(int i=1;i<=n;++i) printf("%lld ",query(1,1,n,i,i));
return 0;
}