f不够,加上g
g的转移?要特别注意没有直接访问的点。分5类点。
大力分类讨论即可。
#include#define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define mid ((l+r)>>1)using namespace std;typedef long long ll;template il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x);}template il void output(T x){ if(x/10)output(x/10);putchar(x%10+'0');}template il void ot(T x){ if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=1e5+5;const int mod=998244353;int n,m;int ad(int x,int y){ return x+y>=mod?x+y-mod:x+y;}int mul(int x,int y){ return (ll)x*y%mod;}struct node{ int f,g,sumf; int mf,mg;}t[4*N];int T;void pushup(int x){ t[x].sumf=ad(ad(t[x<<1].sumf,t[x<<1|1].sumf),t[x].f);}void build(int x,int l,int r){ if(l==r){ t[x].g=1;t[x].f=0;t[x].mf=1;t[x].mg=1; return; } t[x].g=1;t[x].mf=1;t[x].mg=1; build(x<<1,l,mid); build(x<<1|1,mid+1,r);}void pushdown(int x){ for(reg i=0;i<=1;++i){ int son=(x<<1)|i; t[son].mf=mul(t[son].mf,t[x].mf); t[son].f=mul(t[son].f,t[x].mf); t[son].sumf=mul(t[son].sumf,t[x].mf); t[son].mg=mul(t[son].mg,t[x].mg); t[son].g=mul(t[son].g,t[x].mg); } t[x].mf=1;t[x].mg=1;}void upda(int x,int l,int r,int L,int R){ if(L<=l&&r<=R){ //2 t[x].sumf=ad(mul(ad(t[x].sumf,mod-t[x].f),2),ad(t[x].f,T)); t[x].f=ad(t[x].f,T); t[x].mf=mul(t[x].mf,2);//4// cout<<" f "< <<" sumf "< <