问题可以转化为每次区间覆盖操作有 (frac{1}{2}) 的概率进行，求标记和的期望。于是我们只要求出所有点有标记的概率即可。
我们设 (f_i) 表示节点 (i) 有标记的概率， (g_i) 表示节点 (i) 的祖先节点有标记的概率。如果一个节点未完全被包含，那么其未被包含的节点是否有标记取决于其祖先节点是否有标记，故要用来自祖先节点的信息来更新答案（设未包含的节点为 (j) ，那么 (f_j leftarrow frac{f_j+g_j}{2}) ）。如果一个节点被完全包含，那么 (f_i leftarrow frac{f_i+1}{2}) ，其所有子节点(包括自己) (g_j leftarrow frac{g_j+1}{2}) ； 否则因为当前到达的区间标记已被下传，所以 (f_ileftarrow frac{f_i}{2}, g_ileftarrow frac{g_i}{2}) 。 线段树维护 (f_i,g_i) ， (g_i) 的维护需要打标记。
#include<cstdio>
#include<cassert>
inline int gi()
{
char c=getchar(); int x=0;
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';
return x;
}
const int N=2e5+5,Mod=998244353,inv=Mod+1>>1;
int n,m,f[N<<2],g[N<<2],sum[N<<2],tg1[N<<2],tg2[N<<2],fm=1;
#define lx (x<<1)
#define rx (x<<1|1)
#define mul(x,y) (1ll*(x)*(y)%Mod)
#define div2(x) (1ll*(x)*inv%Mod)
void pushdown(int x)
{
if(tg1[x]==1&&tg2[x]==0) return ;
tg1[lx]=mul(tg1[lx],tg1[x]),tg1[rx]=mul(tg1[rx],tg1[x]);
tg2[lx]=(mul(tg2[lx],tg1[x])+tg2[x])%Mod;
tg2[rx]=(mul(tg2[rx],tg1[x])+tg2[x])%Mod;
g[lx]=(mul(g[lx],tg1[x])+tg2[x])%Mod;
g[rx]=(mul(g[rx],tg1[x])+tg2[x])%Mod;
tg1[x]=1,tg2[x]=0;
}
void solve(int x)
{
f[x]=div2((f[x]+g[x])%Mod);
sum[x]=((sum[lx]+sum[rx])%Mod+f[x])%Mod;
}
void update(int x, int l, int r, int sl, int sr)
{
if(sl<=l&&r<=sr)
{
f[x]=div2(f[x]+1);
g[x]=div2(g[x]+1);
sum[x]=((sum[lx]+sum[rx])%Mod+f[x])%Mod;
tg1[x]=div2(tg1[x])%Mod;
tg2[x]=(div2(tg2[x])+inv)%Mod;
return ;
}
pushdown(x);
f[x]=div2(f[x]),g[x]=div2(g[x]);
int mid=l+r>>1;
if(sl>mid)
update(rx,mid+1,r,sl,sr),solve(lx);
else if(sr<=mid)
update(lx,l,mid,sl,sr),solve(rx);
else update(lx,l,mid,sl,sr),update(rx,mid+1,r,sl,sr);
sum[x]=((sum[lx]+sum[rx])%Mod+f[x])%Mod;
}
int main()
{
n=gi(),m=gi();
for(int i=1;i<=(n<<2);++i) tg1[i]=1;
while(m--)
{
int op=gi();
if(op==2) printf("%d
",1ll*fm*sum[1]%Mod);
else
{
fm=2ll*fm%Mod;
int l=gi(),r=gi();
update(1,1,n,l,r);
}
}
}