link

首先这题显然可以转化为求每个节点有标记的线段树个数之和

这$2^k$(k为修改次数)个线段树显然相当于对于每个修改改或不改得到的所有线段树。

就可以转化为每个修改有$\frac{1}{2}$的概率修改,每个点有标记的概率之和$\cdot 2^k$。

维护一下每个点有标记的概率$f$。

考虑每个修改。

  1. 如果这个点标记要下传,那么$f=f\cdot \frac{1}{2}$。
  2. 如果这个点要打标记,那么$f=f\cdot \frac{1}{2}+\frac{1}{2}$。
  3. 如果这个点要从父亲得到标记?

发现操作之后的概率和到根路径上有标记的概率有关。那么就多维护每个点到根路径上有标记的概率$g$。

对于情况1,$g=g\cdot \frac{1}{2}$。

对于情况2,$g=g\cdot \frac{1}{2}+\frac{1}{2}$,并且子树中每个节点的$g$都要$=g\cdot \frac{1}{2}+\frac{1}{2}$。

对于情况3,$f=f\cdot\frac{1}{2}+g\cdot\frac{1}{2}$。

对于其它的点呢?

显然不会有影响。

所以维护一下区间乘区间加标记,就可以了。

const int p=998244353,i2=(p+1)>>1;
int pw[100005],ans,now;
struct smt{
    int ls,rs,sum,f,g,add,mul;
    smt *l,*r;
    smt(int la,int ra){
        ls=la;rs=ra;
        add=0;mul=1;
        f=g=0;
        sum=0;
        if(la==ra){
            l=r=0;return;
        }
        int mid=(ls+rs)>>1;
        l=new smt(ls,mid);
        r=new smt(mid+1,rs);
    }    
    void put_tag(int x,int y){
        g=(g*x+y)%p;
        add=(add*x+y)%p;
        mul=mul*x%p;
    }
    void push_down(){
        if(l){
            l->put_tag(mul,add);
            r->put_tag(mul,add);
        }    
        mul=1;add=0;
    }
    void push_up(){
        sum=f;
        if(l)sum=(sum+l->sum+r->sum)%p;
    }
    void push(){
        f=(f+g)*i2%p;
        push_up();
    }
    void work(int la,int ra){
        push_down();
        if(la<=ls && rs<=ra){
            f=(f*i2+i2)%p;
            put_tag(i2,i2);
            push_up();
            return;
        }
        f=f*i2%p;
        g=g*i2%p;
        if(la<=l->rs)l->work(la,ra);
        else l->push();
        if(r->ls<=ra)r->work(la,ra);
        else r->push();
        push_up();
    }
};
smt *rt;
signed main(){
#ifdef QAQAutoMaton 
    freopen("segment.in","r",stdin);
    freopen("segment.out","w",stdout);
#endif
    int n,q,tp,l,r;
    read(n,q);
    pw[0]=1;
    rt=new smt(1,n);
    for(int i=1;i<=q;++i)pw[i]=pw[i-1]*2%p;
    for(;q;--q){
        read(tp);
        if(tp==2)write(rt->sum*pw[now]%p,'\n');
        else{
            read(l,r);
            ++now;
            rt->work(l,r);
        }
    }
    return 0;
}

标签: 线段树, 概率

添加新评论