ZJOI2019 线段树

---

神仙题orz

先看一眼显然不可做。。。就去膜题解了。。

然而知道怎么设状态以后自己xjb推也能推出来

设\(f[i][0]\)为第\(i\)个点为黑色(1)的线段树数量；

设\(f[i][1]\)为第\(i\)个点为白色(0)且\(i\)的祖先上有黑点的线段树数量；

设\(f[i][2]\)为第\(i\)个点为白色且\(i\)的祖先全是白点的线段树数量。

对于线段树上的点分类讨论。，

1. 被完全覆盖的点，而且会被染黑，就是正常线段树需要修改的那些点。显然一定变黑。
   \((f_0,f_1,f_2)\rightarrow(2f_0+f_1+f_2,f_1,f_2)\)
   注意如果线段树没有被修改还是要维持原状。
2. 被完全覆盖的点，但是正常线段树不会修改到它，只会修改到父亲。也就是1类点的后代。
   这样的点不会被染黑，但是祖先一定变黑。
   \((f_0,f_1,f_2)\rightarrow(2f_0,2f_1+f_2,f_2)\)
3. 在正常线段树上经过但是没有染黑的点。这些点会被pushdown，也就是一定变白。它的祖先也都会变白。
   \((f_0,f_1,f_2)\rightarrow(f_0,f_1,f_0+f_1+2f_2)\)
4. 不被覆盖的点，但是它的父亲是3类点，会接受父亲的pushdown。如果有祖先是黑色的这个点就会变黑。
   \((f_0,f_1,f_2)\rightarrow(2f_0+f_1,f_1,2f_2)\)
5. 剩下的点，也就是不被覆盖也不会接受pushdown的点。这些点显然不会有变化。
   \((f_0,f_1,f_2)\rightarrow(2f_0,2f_1,2f_2)\)

为了减小常数，可以把设的状态从方案数改为概率，那么转移的时候全都除以\(2\)就好了。这样可以去掉第5类点的转移。

其他4类点只需要在正常线段树上跑一遍就行了，操作都是区间乘矩阵，其中第2类点要用lazy标记。

#include
    
     #define il inline#define vd void#define mod 998244353#define inv2 499122177typedef long long ll;il ll gi(){    ll x=0,f=1;    char ch=getchar();    while(!isdigit(ch)){        if(ch=='-')f=-1;        ch=getchar();    }    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return x*f;}struct matrix{    int f00,f01,f02,f10,f11,f12,f20,f21,f22;    matrix(){f00=f01=f02=f10=f11=f12=f20=f21=f22=0;}};matrix I,dp1,dp2,dp3,dp4;il vd dp_init(){    I.f00=I.f11=I.f22=1;    dp1.f00=1;dp1.f10=dp1.f20=dp1.f11=dp1.f22=inv2;    dp2.f00=dp2.f11=1;dp2.f21=dp2.f22=inv2;    dp3.f22=1;dp3.f00=dp3.f11=dp3.f02=dp3.f12=inv2;    dp4.f00=dp4.f22=1;dp4.f10=dp4.f11=inv2;}il bool isI(const matrix&x){return x.f00==1&&!x.f01&&!x.f02&&!x.f10&&x.f11==1&&!x.f12&&!x.f20&&!x.f21&&x.f22==1;}il matrix operator*(const matrix&a,const matrix&b){    matrix ret;    ret.f00=(1ll*a.f00*b.f00+1ll*a.f01*b.f10+1ll*a.f02*b.f20)%mod;    ret.f01=(1ll*a.f00*b.f01+1ll*a.f01*b.f11+1ll*a.f02*b.f21)%mod;    ret.f02=(1ll*a.f00*b.f02+1ll*a.f01*b.f12+1ll*a.f02*b.f22)%mod;    ret.f10=(1ll*a.f10*b.f00+1ll*a.f11*b.f10+1ll*a.f12*b.f20)%mod;    ret.f11=(1ll*a.f10*b.f01+1ll*a.f11*b.f11+1ll*a.f12*b.f21)%mod;    ret.f12=(1ll*a.f10*b.f02+1ll*a.f11*b.f12+1ll*a.f12*b.f22)%mod;    ret.f20=(1ll*a.f20*b.f00+1ll*a.f21*b.f10+1ll*a.f22*b.f20)%mod;    ret.f21=(1ll*a.f20*b.f01+1ll*a.f21*b.f11+1ll*a.f22*b.f21)%mod;    ret.f22=(1ll*a.f20*b.f02+1ll*a.f21*b.f12+1ll*a.f22*b.f22)%mod;    return ret;}il matrix operator+(const matrix&a,const matrix&b){    matrix ret;    ret.f00=a.f00+b.f00;if(ret.f00>=mod)ret.f00-=mod;    ret.f01=a.f01+b.f01;if(ret.f01>=mod)ret.f01-=mod;    ret.f02=a.f02+b.f02;if(ret.f02>=mod)ret.f02-=mod;    ret.f10=a.f10+b.f10;if(ret.f10>=mod)ret.f10-=mod;    ret.f11=a.f11+b.f11;if(ret.f11>=mod)ret.f11-=mod;    ret.f12=a.f12+b.f12;if(ret.f12>=mod)ret.f12-=mod;    ret.f20=a.f20+b.f20;if(ret.f20>=mod)ret.f20-=mod;    ret.f21=a.f21+b.f21;if(ret.f21>=mod)ret.f21-=mod;    ret.f22=a.f22+b.f22;if(ret.f22>=mod)ret.f22-=mod;    return ret;}matrix sum[400010],w[400010],lazy[400010];#define mid ((l+r)>>1)il vd upd(int x,int l,int r){if(l==r)sum[x]=w[x];else sum[x]=sum[x<<1]+w[x]+sum[x<<1|1];}il vd upd(int x){sum[x]=sum[x<<1]+w[x]+sum[x<<1|1];}il vd build(int x,int l,int r){    w[x].f02=1;lazy[x]=I;if(l==r){sum[x]=w[x];return;}    build(x<<1,l,mid),build(x<<1|1,mid+1,r);    upd(x);}il vd Upd(int x,const matrix&o){sum[x]=sum[x]*o;w[x]=w[x]*o;lazy[x]=lazy[x]*o;}il vd pushdown(int x){    if(!isI(lazy[x])){        sum[x<<1]=sum[x<<1]*lazy[x],w[x<<1]=w[x<<1]*lazy[x];lazy[x<<1]=lazy[x<<1]*lazy[x];        sum[x<<1|1]=sum[x<<1|1]*lazy[x],w[x<<1|1]=w[x<<1|1]*lazy[x];lazy[x<<1|1]=lazy[x<<1|1]*lazy[x];        lazy[x]=I;    }}il vd update(int x,int l,int r,const int&L,const int&R){    if(L<=l&&r<=R){        w[x]=w[x]*dp1;        if(l==r)sum[x]=w[x];        else{            Upd(x<<1,dp2),Upd(x<<1|1,dp2);            upd(x);        }        return;    }    pushdown(x);    w[x]=w[x]*dp3;    if(L<=mid)update(x<<1,l,mid,L,R);    else w[x<<1]=w[x<<1]*dp4,upd(x<<1,l,mid);    if(mid
     
      <<1|1,mid+1,r,L,R);    else w[x<<1|1]=w[x<<1|1]*dp4,upd(x<<1|1,mid+1,r);    upd(x);}#undef midint main(){#ifdef XZZSB    freopen("in.in","r",stdin);    freopen("out.out","w",stdout);#endif    dp_init();    int n=gi(),m=gi(),op,l,r,p2=1;    build(1,1,n);    while(m--){        op=gi();        if(op==1)l=gi(),r=gi(),update(1,1,n,l,r),p2=p2*2%mod;        else printf("%lld\n",1ll*sum[1].f00*p2%mod);    }    return 0;}