P5280 ZJOI2019 线段树

#include <bits/stdc++.h>
using namespace std;
const long long N=600005,MOD=998244353;
long long n,m,g[N],f[N],tf[N],tg[N],ans[N],k=1;
void build(long long o,long long l,long long r){
	g[o]=tf[o]=tg[o]=1;
	if(l==r)return ;
	long long mid=(l+r)/2;
	build(o*2,l,mid),build(o*2+1,mid+1,r);
}
void pushtf(long long o,long long x){
	f[o]=(f[o]*x)%MOD,tf[o]=(tf[o]*x)%MOD,ans[o]=(ans[o]*x)%MOD;
}
void pushtg(long long o,long long x){
	g[o]=(g[o]*x)%MOD,tg[o]=(tg[o]*x);
}
void pushdown(long long o){
//	if(tf[o]!=1){
		pushtf(o*2,tf[o]),pushtf(o*2+1,tf[o]),tf[o]=1;	
//	}
//	if(tg[o]!=1){
		pushtg(o*2,tg[o]),pushtg(o*2+1,tg[o]),tg[o]=1;	
//	}
}
void pushup(long long o){
	ans[o]=(f[o]+(ans[o*2]+ans[o*2+1])%MOD)%MOD;
}
void cha(long long o,long long L,long long R,long long l,long long r){
	pushdown(o);
	
	if(l==L&&r==R){
		f[o]=(f[o]+k)%MOD;
		pushtf(o*2,2),pushtf(o*2+1,2);
	}else{
		long long mid=(l+r)/2;
		long long uu=o*2+1,ll=o*2;
		g[o]=(g[o]+k)%MOD;
		if(R<=mid){
			cha(ll,L,R,l,mid);
		    pushdown(uu);
		  	f[uu]=(f[uu]+((k-g[uu]+MOD)%MOD))%MOD;
			g[uu]=(g[uu]*2)%MOD;
			pushtg(uu*2,2ll),pushtg(uu*2+1,2ll);
			pushtf(uu*2,2ll),pushtf(uu*2+1,2ll);
			pushup(uu);
		}else{
			if(L>mid){
				cha(uu,L,R,mid+1,r);
				pushdown(ll);
				f[ll]=(f[ll]+((k-g[ll]+MOD)%MOD))%MOD;
				g[ll]=(g[ll]*2)%MOD;
				pushtg(ll*2,2ll),pushtg(ll*2+1,2ll);
				pushtf(ll*2,2ll),pushtf(ll*2+1,2ll);
				pushup(ll);
			}else{
				cha(ll,L,mid,l,mid);
				cha(uu,mid+1,R,mid+1,r);
			}
		}
	}
	pushup(o);
}
int main(){
	cin>>n>>m;
	build(1,1,n);
	long long op,ll,rr;
	for(long long i=1;i<=m;i++){
		cin>>op;
		if(op==1){
			cin>>ll>>rr;
			cha(1,ll,rr,1,n);
			k=k*2ll%MOD;
		}else{
			 cout<<ans[1]<<"\n";
		}
	}
}