神题，神题

首先有一个思想就是计数转概率期望，我们发现每次复制一遍线段树最后会有\(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
    
     #define re register#define LL long longinline 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]
     
      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\n",1ll*pw*ans%mod);        else {            x=read(),y=read();pw=(pw+pw)%mod;            change(x,y,1);        }    }    return 0;}