维护左子树右子树的贡献和跨区间贡献
#includeusing namespace std;typedef long long LL;const LL maxn=10000000;const LL inf=2147483646;const LL MOD=998244353;#define md(x) (x=(x>MOD)?x-MOD:x)#define ctwo(x) ((x*(x-1)/2+x)%MOD)#define dec(x) (x=x?x-1:MOD-1)#define inc(x) (x=(x==MOD-1)?0:x+1)inline LL Read(){ LL x=0,f=1; char c=getchar(); while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f;}struct node{ LL son[2],pre,suf,ans,flag;}tree[maxn];LL n,m,nod,root;inline void mg(node& now,const node& son0,const node& son1){ now.pre=son0.pre+son0.flag*son1.pre; md(now.pre); now.suf=son1.suf+son1.flag*son0.suf; md(now.suf); now.ans=(son0.ans+son1.ans+son0.suf*son1.pre)%MOD; if(now.flag){ if(!(son0.flag&&son1.flag)) inc(now.pre), inc(now.suf), inc(now.ans); } else if(son0.flag&&son1.flag) dec(now.pre), dec(now.suf), dec(now.ans);}inline void Update(LL now,LL son0,LL son1,LL len1,LL len2){ if(len1==0){ tree[now].flag=tree[now].pre=tree[now].suf=tree[now].ans=0; return; } node c1,c2; if(son0) c1=tree[son0]; else{ len1=len1%MOD, c1.ans=ctwo(len1), c1.pre=len1, c1.suf=len1, c1.flag=1; } if(son1) c2=tree[son1]; else{ len2=len2%MOD, c2.ans=ctwo(len2), c2.pre=len2, c2.suf=len2, c2.flag=1; } mg(tree[now],c1,c2);}inline void Change(LL now,LL l,LL r,LL lt,LL rt){ if(lt==l&&rt==r){ tree[now].flag=0, Update(now,tree[now].son[0],tree[now].son[1],(r-l)>>1,(r-l+1)>>1); return; } LL mid=(l+r)>>1; if(mid>lt){ if(!tree[now].son[0]){ tree[now].son[0]=++nod; LL len=(mid-l)%MOD,son0=nod; tree[son0].ans=ctwo(len), tree[son0].pre=len, tree[son0].suf=len, tree[son0].flag=1; } Change(tree[now].son[0],l,mid,lt,min(rt,mid)); } if(mid