分析:
“如果你对树状数组比较熟悉，不难发现可怜求的是后缀和”
设数列为(A)，那么可怜求的就是(A_{l-1})到(A_{r-1})的和（即(l-1)的后缀减(r)的后缀，(sum_{i=l-1}^{r-1}A_i)）,而答案为(A_l)到(A_r)的和（即(sum_{i=l}^{r}A_i)）这两种答案都包含(A_l)到(A_{r-1})的和，因此只需判断(A_{l-1})与(A_r)相等的概率就行了
那么怎么算？
考虑记下每次修改的影响，假设已知左端点(a)和右端点(b)，那么对于某一次修改区间(l)~(r)，则只有当(ain[l,r])或(bin[l,r])时才有影响，设(p)为任选区间内一个数的概率，这里分三种情况讨论:
- (ain[1,l-1]),(bin[l,r])时，有(1-p)的概率不影响
- (ain[l,r]),(bin[l,r])时，有(1-2*p)的概率不影响
- (ain[l,r]),(bin[r+1,n])时，有(1-p)的概率不影响
那么只要把所有的影响都合并起来就行了，设当前相同概率为(p)，当前修改不影响的概率(q)，则相同概率更新为(p*q+(1-p)*(1-q))
但是直接朴素必然TLE，因此我们要寻找更高效的算法
考虑二维线段树，设点((x,y))表示(A_x)与(A_y)相等的概率，那么我们会惊奇的发现：
这不就是区间修改单点查询吗！
每读入一个修改，就用上面所说的影响更新区间，即([1,l-1,l,r],[l,r,l,r],[l,r,r+1,n])三个区间，用上述式子合并区间
询问即查询点((l-1,r))的值
还有一个坑点！！(l)可能为(1)！！
(l=1)时，可怜求的是(r)的后缀和，因此我们需要求(r)的后缀和与前缀和相等的概率
这也可以用类似方法，第一维我们新增一个元素(0)，用([0,x])表示(x)的后缀和与前缀和相等的概率，那么当修改区间([l,r])时，区间([1,l-1]),([r+1,n])中元素的后缀和与前缀和一定会被影响，即不被影响概率为(0)；而区间([l,r])中元素有(p)的概率不被影响（即正好选到它，(p)的意义即为上述），这时我们也要更新。这样当(l=1)时，直接查询点((l-1,r))的值即可
还有就是卡卡常数，卡卡空间
以及线段树要动态开点
Code:
（代码丑不要怪我）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<iomanip>
#include<algorithm>
using namespace std;
const int N=100010;
const int MOD=998244353;
int rt[N*21],n,cnt;
struct tree
{
int l,r;
int v;//卡空间，开int
}tr[N*402];
inline long long mul(long long p,long long q)//p*q+(1-p)*(1-q)
{
long long res=p*q%MOD;
res=(res+(1-p+MOD)*(1-q+MOD)%MOD)%MOD;
return res;
}
inline long long power(long long x,long long y)//快速幂
{
long long ans=1;
while(y)
{
if(y&1) ans=ans*x%MOD;
x=x*x%MOD,y>>=1;
}
return ans;
}
inline void updatay(int l,int r,int &id,int ly,int ry,long long p)//修改区间二维
{
if(id==0)
{
cnt++;
id=cnt;
tr[id].v=1;//初始时都是0，因此相等概率为1
}
if(l>=ly&&r<=ry)
{
tr[id].v=mul(p,tr[id].v);
return;
}
int mid=l+r>>1;
if(ly<=mid) updatay(l,mid,tr[id].l,ly,ry,p);
if(ry>mid) updatay(mid+1,r,tr[id].r,ly,ry,p);
}
inline void updatax(int l,int r,int id,int lx,int rx,int ly,int ry,long long p)//修改区间一维
{
if(l>=lx&&r<=rx)
{
updatay(1,n,rt[id],ly,ry,p);
return;
}
int mid=l+r>>1;
if(lx<=mid) updatax(l,mid,id<<1,lx,rx,ly,ry,p);
if(rx>mid) updatax(mid+1,r,id<<1|1,lx,rx,ly,ry,p);
}
long long quey(int l,int r,int id,int y)//查询二维
{
if(id==0) return 1;//初始时都是0，因此相等概率为1
if(l==r) return tr[id].v;
int mid=l+r>>1;
long long res;
if(y<=mid) res=mul(tr[id].v,quey(l,mid,tr[id].l,y));
else res=mul(tr[id].v,quey(mid+1,r,tr[id].r,y));
//合并沿途所有区间影响值
return res;
}
long long quex(int l,int r,int id,int x,int y)//查询一维
{
if(l==r) return quey(1,n,rt[id],y);
int mid=l+r>>1;
if(x<=mid) return mul(quey(1,n,rt[id],y),quex(l,mid,id<<1,x,y));
else return mul(quey(1,n,rt[id],y),quex(mid+1,r,id<<1|1,x,y));
//合并沿途所有区间影响值
}
int main()
{
int i,j,k,q,op,l,r;
long long p;
scanf("%d%d",&n,&q);
cnt=0;
while(q--)
{
scanf("%d%d%d",&op,&l,&r);
if(op==1)
{
p=power(r-l+1,MOD-2);//求逆元，即选某一个元素的概率
if(l>1) updatax(0,n,1,1,l-1,l,r,(1-p+MOD)%MOD),updatax(0,n,1,0,0,1,l-1,0);
if(r<n) updatax(0,n,1,l,r,r+1,n,(1-p+MOD)%MOD),updatax(0,n,1,0,0,r+1,n,0);
updatax(0,n,1,l,r,l,r,(1-p*2%MOD+MOD)%MOD),updatax(0,n,1,0,0,l,r,p);
}
else printf("%lld
",quex(0,n,1,l-1,r));
}
return 0;
}