ZJOI2019 线段树
首先这题显然可以转化为求每个节点有标记的线段树个数之和
这\(2^k\)(k为修改次数)个线段树显然相当于对于每个修改改或不改得到的所有线段树。
就可以转化为每个修改有\(\frac{1}{2}\)的概率修改，每个点有标记的概率之和\(\cdot 2^k\)。
维护一下每个点有标记的概率\(f\)。
考虑每个修改。
- 如果这个点标记要下传，那么\(f=f\cdot \frac{1}{2}\)。
- 如果这个点要打标记，那么\(f=f\cdot \frac{1}{2}+\frac{1}{2}\)。
- 如果这个点要从父亲得到标记？
发现操作之后的概率和到根路径上有标记的概率有关。那么就多维护每个点到根路径上有标记的概率\(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;
}