看到这题，首先想到将求和转期望，即每次操作进行概率为1/2，求节点打标记概率。
首先对于每次区间修改操作，对节点进行分类：
1、这个点和其父亲都和修改区间无交，这种情况可以无视。
2、这个点和修改区间无交但父亲和修改区间有交，这样该区间有无标记只和本身及是否存在一个祖先有标记相关。
3、这个点被修改区间覆盖，且父节点也被覆盖，则无变化。
4、这个点和修改区间有交但没有被完全包含，则不会有标记（因为要pushdown）。
然后记录该节点有标记的概率f，和祖先至少有一个有标记的概率g，然后根据上面表述的意思转移即可。
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N=2e5+,mod=,inv2=;
int n,m,pw[N],inv[N],f[N<<],g[N<<],s[N<<],tag[N<<];
void pushup(int rt){s[rt]=(1ll*s[rt<<]+s[rt<<|]+f[rt])%mod;}
void modify(int rt,int v){g[rt]=1ll*(g[rt]+pw[v]-)*inv[v]%mod,tag[rt]+=v;}
void pushdown(int rt)
{
if(!tag[rt])return;
modify(rt<<,tag[rt]),modify(rt<<|,tag[rt]);
tag[rt]=;
}
void update(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
tag[rt]++,f[rt]=1ll*(f[rt]+)*inv2%mod,g[rt]=1ll*(g[rt]+)*inv2%mod;
pushup(rt);return;
}
if(L>r||R<l)
{
f[rt]=1ll*(f[rt]+g[rt])*inv2%mod;
pushup(rt);return;
}
pushdown(rt);
int mid=l+r>>;
f[rt]=1ll*f[rt]*inv2%mod,g[rt]=1ll*g[rt]*inv2%mod;
update(L,R,lson),update(L,R,rson);
pushup(rt);
}
int main()
{
scanf("%d%d",&n,&m);
pw[]=inv[]=;for(int i=;i<=n;i++)pw[i]=2ll*pw[i-]%mod,inv[i]=1ll*inv[i-]*inv2%mod;
int num=;
while(m--)
{
int op,l,r;scanf("%d",&op);
if(op==)printf("%d\n",1ll*s[]*num%mod);
else scanf("%d%d",&l,&r),num=2ll*num%mod,update(l,r,,n,);
}
}