ZJOI2019 线段树

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}$。

对于其它的点呢?

显然不会有影响。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×