题解 [ABC332F] Random Update Query

· · 题解

相对于过往比赛的 F 应该算正常难度，但是这个概率与期望相对于 E 的状态压缩动态规划要略简单一点。

题意

题意翻译很清楚。

分析

根据期望的定义，EX=\sum x_ip_i。

对于第 i 个数，第 j 次操作，对于任意的 L_j \le i \le R_j，那么这一次操作选中一个数赋值的概率是 P_j=\dfrac{1}{R_j-L_j+1}，所以 E_i = E_i(1-P_j)+X_jP_j。

关注到这是一个区间加乘的操作，所以直接复制 P2023 [AHOI2009] 维护序列 的线段树模板就行。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define M(s) (s)%=p 
using namespace std;
typedef long long LL;
const LL p=998244353;
int n,m;
LL qpow(LL a,LL b){
    LL ret=1;
    for(;b;b>>=1,a=a*a%p)if(b&1)ret=ret*a%p;
    return ret%p;
}
LL a[200002],sum[800008];
LL add[800008],mul[800008];
void build(int rt,int l,int r){
    if(l==r){
        sum[rt]=a[l];
        mul[rt]=1;
        return;
    }
    int m=(l+r)/2;
    build(rt*2,l,m);
    build(rt*2+1,m+1,r);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
    mul[rt]=mul[rt*2]=mul[rt*2+1]=1;
}
void push_down(int rt,int l,int r){
    int m=(l+r)/2;
    sum[rt*2]*=mul[rt];M(sum[rt*2]);
    sum[rt*2]+=add[rt]*(m-l+1);M(sum[rt*2]);
    add[rt*2]*=mul[rt];M(add[rt*2]);
    add[rt*2]+=add[rt];M(add[rt*2]);
    mul[rt*2]*=mul[rt];M(mul[rt*2]);
    sum[rt*2+1]*=mul[rt];M(sum[rt*2+1]);
    sum[rt*2+1]+=add[rt]*(r-m);M(sum[rt*2+1]);
    add[rt*2+1]*=mul[rt];M(add[rt*2+1]);
    add[rt*2+1]+=add[rt];M(add[rt*2+1]);
    mul[rt*2+1]*=mul[rt];M(mul[rt*2+1]);
    mul[rt]=1,add[rt]=0; 
}
void update(int rt,int l,int r,int L,int R,LL val,int op){
    if(L<=l && r<=R){
        if(op==0){
            sum[rt]+=val*(r-l+1);M(sum[rt]);
            add[rt]+=val;M(add[rt]);
        }
        else{
            sum[rt]*=val;M(sum[rt]);
            add[rt]*=val;M(add[rt]);
            mul[rt]*=val;M(mul[rt]);
        }
        return;
    }
    push_down(rt,l,r);
    int m=(l+r)/2;
    if(m>=L) update(rt*2,l,m,L,R,val,op);
    if(m<R) update(rt*2+1,m+1,r,L,R,val,op);
    sum[rt]=sum[rt*2]%p+sum[rt*2+1]%p;
    sum[rt]%=p;
}
LL query(int rt,int l,int r,int L,int R){
    if(L<=l && r<=R) return sum[rt];
    push_down(rt,l,r);
    int m=(l+r)/2;
    LL ret=0;
    if(L<=m){ret+=query(rt*2,l,m,L,R);M(ret);}
    if(m<R){ret+=query(rt*2+1,m+1,r,L,R);M(ret);}
    return ret;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int l,r,x;m--;){
        scanf("%d%d%d",&l,&r,&x);
        int len=r-l+1,inv=qpow(len,p-2);//求出 1/(r-l+1)。
        update(1,1,n,l,r,(LL)(len-1)*inv%p,1);//区间乘。
        update(1,1,n,l,r,(LL)x*inv%p,0);//区间加。
    }
    for(int i=1;i<=n;i++) printf("%lld ",query(1,1,n,i,i));
    return 0;
}