神题，神题
首先有一个思想就是计数转概率期望，我们发现每次复制一遍线段树最后会有(2^m)棵线段树过于自闭，于是我们把这个问题转化成一个概率问题，对于每次修改操作，我们另其只有(frac{1}{2})的概率发生，这样我们维护每个点是(1)的概率，最后乘上总情况数就是答案了
于是我们设(dp_i)表示线段树上(i)节点(operatorname{tag=1})的概率，我们对于线段树上的点分成三类
- 修改操作中实际经过的点
对于这些点，如果这次修改操作发生，那么这个点的(operatorname{tag})肯定被(operatorname{pushdown})掉了，于是肯定是(0)，所以对于这类点(dp_i=dp_i/2)
- 最后被打(operatorname{tag})的点
如果修改操作发生，那么(operatorname{tag})肯定为(1)，所以直接(dp_i=(dp_i+1)/2)
- 其父亲被访问到，但是这个节点本身吗没有被访问到
大力思考后会发现这类点没有办法维护，能影响这类点只有(operatorname{pushdown})，而一旦这个点到根的路径上有(1)，那么这个(1)就一定会被(operatorname{pushdown})到这个点上来，所以我们需要维护一下每个到根的路径上的情况
于是设(t_i)表示节点(i)到根的路径上(operatorname{tag})全部为(0)的概率
首先考虑(t_i)的修改问题
对于第一类点，显然修改进行的话这个点到根就被清空了，于是(t_i=(t_i+1)/2)
对于第二类点，修改进行这点以及这个点子树里的点到根上就都会至少有这一个点(operatorname{tag=1})，所以这个节点子树内部都会有(t_i=t_i/2)，这个我们直接打上标记就好了
对于第二类点，首先现在有了这个(dp_i)随便搞搞就能维护出来了，考虑一下对于这种点我们只是利用(operatorname{pushdown})把这个点到根的路径上点的(operatorname{tag})推到了这个点上，所以对于这个点及其子树内部的(t_i)没有影响
所以直接写个线段树模拟一下就好了
代码
#include<bits/stdc++.h>
#define re register
#define LL long long
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=998244353;
const int Inv=mod+1>>1;
const int maxn=1e5+5;
int l[maxn<<2],r[maxn<<2],dp[maxn<<2],t[maxn<<2];
int tag[maxn<<2],n,m,pw=1,ans;
void build(int x,int y,int i) {
l[i]=x,r[i]=y;t[i]=tag[i]=1;
if(x==y) return;
int mid=x+y>>1;
build(x,mid,i<<1),build(mid+1,y,i<<1|1);
}
inline void pushdown(int i) {
if(tag[i]==1) return;
tag[i<<1]=1ll*tag[i<<1]*tag[i]%mod;
tag[i<<1|1]=1ll*tag[i<<1|1]*tag[i]%mod;
t[i<<1]=1ll*t[i<<1]*tag[i]%mod;
t[i<<1|1]=1ll*t[i<<1|1]*tag[i]%mod;
tag[i]=1;
}
void change(int x,int y,int i) {
if(x<=l[i]&&y>=r[i]) {
ans=(ans-dp[i]+mod)%mod;
dp[i]=1ll*(dp[i]+1)*Inv%mod;
t[i]=1ll*t[i]*Inv%mod;
tag[i]=1ll*tag[i]*Inv%mod;
ans=(ans+dp[i])%mod;
return;
}
if(r[i]<x||l[i]>y) {
ans=(ans-dp[i]+mod)%mod;
int v=(mod+1-dp[i])%mod;
dp[i]=1ll*(v+t[i]%mod)%mod*Inv%mod;
dp[i]=(mod+1-dp[i])%mod;
ans=(ans+dp[i])%mod;
return;
}
pushdown(i);
change(x,y,i<<1),change(x,y,i<<1|1);
t[i]=1ll*(t[i]+1)*Inv%mod;
ans=(ans-dp[i]+mod)%mod;
dp[i]=1ll*dp[i]*Inv%mod;
ans=(ans+dp[i])%mod;
}
int main() {
n=read(),m=read();build(1,n,1);
int op,x,y;
while(m--) {
op=read();
if(op==2) printf("%d
",1ll*pw*ans%mod);
else {
x=read(),y=read();pw=(pw+pw)%mod;
change(x,y,1);
}
}
return 0;
}