ZJOI2019 线段树
神仙题orz
先看一眼显然不可做。。。就去膜题解了。。
然而知道怎么设状态以后自己xjb推也能推出来
设\(f[i][0]\)为第\(i\)个点为黑色(1)的线段树数量；
设\(f[i][1]\)为第\(i\)个点为白色(0)且\(i\)的祖先上有黑点的线段树数量；
设\(f[i][2]\)为第\(i\)个点为白色且\(i\)的祖先全是白点的线段树数量。
对于线段树上的点分类讨论。，
- 被完全覆盖的点，而且会被染黑，就是正常线段树需要修改的那些点。显然一定变黑。
\((f_0,f_1,f_2)\rightarrow(2f_0+f_1+f_2,f_1,f_2)\)
注意如果线段树没有被修改还是要维持原状。 - 被完全覆盖的点，但是正常线段树不会修改到它，只会修改到父亲。也就是1类点的后代。
这样的点不会被染黑，但是祖先一定变黑。
\((f_0,f_1,f_2)\rightarrow(2f_0,2f_1+f_2,f_2)\) - 在正常线段树上经过但是没有染黑的点。这些点会被pushdown，也就是一定变白。它的祖先也都会变白。
\((f_0,f_1,f_2)\rightarrow(f_0,f_1,f_0+f_1+2f_2)\) - 不被覆盖的点，但是它的父亲是3类点，会接受父亲的pushdown。如果有祖先是黑色的这个点就会变黑。
\((f_0,f_1,f_2)\rightarrow(2f_0+f_1,f_1,2f_2)\) - 剩下的点，也就是不被覆盖也不会接受pushdown的点。这些点显然不会有变化。
\((f_0,f_1,f_2)\rightarrow(2f_0,2f_1,2f_2)\)
为了减小常数，可以把设的状态从方案数改为概率，那么转移的时候全都除以\(2\)就好了。这样可以去掉第5类点的转移。
其他4类点只需要在正常线段树上跑一遍就行了，操作都是区间乘矩阵，其中第2类点要用lazy标记。
#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 998244353
#define inv2 499122177
typedef 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<R)update(x<<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 mid
int 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;
}