分析:
“如果你对树状数组比较熟悉，不难发现可怜求的是后缀和”
设数列为\(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\)，则只有当\(a\in[l,r]\)或\(b\in[l,r]\)时才有影响，设\(p\)为任选区间内一个数的概率，这里分三种情况讨论:
- \(a\in[1,l-1]\),\(b\in[l,r]\)时，有\(1-p\)的概率不影响
- \(a\in[l,r]\),\(b\in[l,r]\)时，有\(1-2*p\)的概率不影响
- \(a\in[l,r]\),\(b\in[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\n",quex(0,n,1,l-1,r));
}
return 0;
}