题目传送门：P3688 [ZJOI2017] 树状数组。
容易发现她求的其实是后缀和，因此只需要计算 \(a_{l-1}=a_r\) 的概率。
假设 \(p_{x,y}\) 表示 \(x,y\) 相同的概率，那么对于一个区间 \([l,r]\)。
- \(x,y\in [l,r]\) 那么 \(x,y\) 有 \(\frac{2}{r-l+1}\) 概率不相同。
- \(x \in [1,l],y\in [l,r]\) 那么 \(x,y\) 有 \(\frac{1}{r-l+1}\) 概率不相同。
- \(x \in (l,r],y\in [r,n]\) 那么 \(x,y\) 有 \(\frac{1}{r-l+1}\) 概率不相同。
然后发现对于一个事件发生的概率为 \(p\)，有 \(q\) 的概率使其不取反，那么新概率即为 \(pq+(1-p)(1-q)\)，然后使用二维线段树维护一下 \(p_{x,y}\) 即可。
有一个特殊情况当 \(l=1\) 是判断是 \(\sum_{i=1}^r a_r = \sum_{i=r}^n a_r\)，与上面情况类似。
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N=1e5+1,mod=998244353;
inline int read(){char c=getchar();int f=1,ans=0;while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
#define lc ls[k]
#define rc rs[k]
int ls[N*350],rs[N*350],add[N*350],root[N<<2],cnt,n,m;
inline int get(int x,int y){return (1ll*x*y%mod+1ll*(1-x+mod)*(1-y+mod)%mod)%mod;}
void exgcd(int a,int b,int &x,int &y){if (b==0) x=1,y=0;else exgcd(b,a%b,y,x),y-=a/b*x;
}
inline int inv(int a){int x,y;exgcd(a,mod,x,y);return (x%mod+mod)%mod;
}
void change(int &k,int l,int r,int l1,int r1,int x){if (l1>r1) return ;if (!k) k=++cnt,add[k]=1;if (l1<=l&&r1>=r){add[k]=get(add[k],x);return ;}int mid=l+r>>1; if (l1<=mid) change(lc,l,mid,l1,r1,x);if (r1>mid) change(rc,mid+1,r,l1,r1,x);
}
int ask(int k,int l,int r,int x){if (!k) return 1;if (l==r) return add[k];int mid=l+r>>1;if (x<=mid) return get(add[k],ask(lc,l,mid,x));else return get(add[k],ask(rc,mid+1,r,x));
}
#undef lc
#undef rc
#define lc k<<1
#define rc k<<1|1
void change(int k,int l,int r,int l1,int r1,int l2,int r2,int x){if (l1>r1) return ;if (l1<=l&&r1>=r){change(root[k],1,n,l2,r2,x);return ;}int mid=l+r>>1;if (l1<=mid) change(lc,l,mid,l1,r1,l2,r2,x);if (r1>mid) change(rc,mid+1,r,l1,r1,l2,r2,x);
}
int ask(int k,int l,int r,int x,int y){if (l==r) return ask(root[k],1,n,y); int mid=l+r>>1;int tmp=ask(root[k],1,n,y);if (x<=mid) return get(tmp,ask(lc,l,mid,x,y));else return get(tmp,ask(rc,mid+1,r,x,y));
}
#undef lc
#undef rc
#define lc ls[k]
#define rc rs[k]
int idx;
struct tree{int add[N<<2],ls[N<<2],rs[N<<2];void change(int &k,int l,int r,int l1,int r1,int x){if (l1>r1) return ;if (!k) k=++idx,add[k]=1;if (l1<=l&&r1>=r){add[k]=get(add[k],x);return ;}int mid=l+r>>1; if (l1<=mid) change(lc,l,mid,l1,r1,x);if (r1>mid) change(rc,mid+1,r,l1,r1,x);}int ask(int k,int l,int r,int x){if (!k) return 1;if (l==r) return add[k];int mid=l+r>>1;if (x<=mid) return get(add[k],ask(lc,l,mid,x));else return get(add[k],ask(rc,mid+1,r,x));}
}tree;
main(){n=read(),m=read();int root;while(m--){int op=read(),l=read(),r=read();if (op==1){int tmp=inv(r-l+1);change(1,1,n,l,r,l,r,1ll*(r-l-1+mod)*tmp%mod);change(1,1,n,1,l-1,l,r,1ll*(r-l)*tmp%mod);change(1,1,n,l,r,r+1,n,1ll*(r-l)*tmp%mod); tree.change(root,1,n,l,r,tmp);tree.change(root,1,n,1,l-1,0);tree.change(root,1,n,r+1,n,0);}else{int tmp;if (l==1) tmp=tree.ask(root,1,n,r);else tmp=ask(1,1,n,l-1,r);printf("%d\n",tmp%mod); }}return 0;
}