[loj3043]线段树

考虑把每一个区间单独统计，令$f[i]$表示第i个区间有标记的次数，$g[i]$表示第i个区间及其祖先中存在标记的次数，然后对于操作将所有区间分为5类（T为已执行操作个数）：

1.被修改，那么$f[i]+=2^{T}$，$g[i]+=2^{T}$（定义修改为执行了$tag=1$）

2.被经过，$f[i]$和$g[i]$都不变（定义经过为执行了pushdown操作）

3.其父亲被经过且自己没有被修改或经过，那么$f[i]+=g[i]$，$g[i]*=2$

4.在被打上标记的点的子树内（不包括被标记点），那么$f[i]*=2$，$g[i]+=2^{T}$

5.不属于以上任何一类，$f[i]*=2$，$g[i]*=2$

维护线段树，123都属于单点修改，45需要区间修改，维护懒标记$(x,y,z)$表示$f[i]=f[i]*x$，$g[i]=g[i]*y+z$，再维护f的和来支持询问即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 800005

 4 #define mod 998244353

 5 #define L (k<<1)

 6 #define R (L+1)

 7 #define mid (l+r>>1)

 8 struct ji{

 9     int x,y,z;

10 }tag[N];

11 int n,m,T,p,l,r,f[N],g[N],sum[N];

12 void upd(int k,ji x){

13     f[k]=1LL*f[k]*x.x%mod;

14     sum[k]=1LL*sum[k]*x.x%mod;

15     g[k]=(1LL*g[k]*x.y+x.z)%mod;

16     tag[k]=ji{1LL*tag[k].x*x.x%mod,1LL*tag[k].y*x.y%mod,(1LL*tag[k].z*x.y+x.z)%mod};

17 }

18 void down(int k,int l,int r){

19     upd(L,tag[k]);

20     upd(R,tag[k]);

21     tag[k]=ji{1,1,0};

22 }

23 void update(int k,int l,int r,int x,int y){

24     if (l!=r)down(k,l,r);

25     if ((l>y)||(x>r)){

26         f[k]=(f[k]+g[k])%mod;

27         g[k]=g[k]*2%mod;

28         upd(L,ji{2,2,0});

29         upd(R,ji{2,2,0});

30         sum[k]=(0LL+sum[L]+sum[R]+f[k])%mod;

31         return;

32     }

33     if ((x<=l)&&(r<=y)){

34         f[k]=(f[k]+T)*(mod+1LL)/2%mod;

35         sum[k]=(0LL+sum[L]+sum[R]+f[k])%mod;

36         upd(k,ji{2,1,T});

37         return;

38     }

39     update(L,l,mid,x,y);

40     update(R,mid+1,r,x,y);

41     sum[k]=(0LL+sum[L]+sum[R]+f[k])%mod;

42 }

43 int main(){

44     scanf("%d%d",&n,&m);

45     T=1;

46     for(int i=1;i<N-4;i++)tag[i]=ji{1,1,0};

47     for(int i=1;i<=m;i++){

48         scanf("%d",&p);

49         if (p==2)printf("%d\n",sum[1]);

50         else{

51             scanf("%d%d",&l,&r);

52             update(1,1,n,l,r);

53             T=2LL*T%mod;

54         }

55     }

56 }

巴特西

[loj3043]线段树

最新文章

热门文章