题意
思路
不难发现，九条カレン醬所写的树状数组，在查询区间 ([1,r]) 的时候，其实在查询后缀 ([r,n]) ；在查询 ([l,r](l eq1)) 的时候，则是在查询 ([l-1,r-1]) 。那么在查询 ([1,r]) 的时候，只需要询问 (r) 的前后缀异或是否相等；在查询 ([l,r](l eq 1)) 的时候，只需要询问 (a[l-1],a[r]) 是否相等。
考虑 (O(n^2)) 的暴力。我们把询问分成上述的两类。第一类询问如果修改到了点 (r) ，则无影响，否则就是相等变不相等的转化，分询问区间盖住 (r) 和不盖住 (r) 两种情况考虑。设原来相等的概率为 (p) ，再进行修改不影响的概率为 (q) ，那么修改后相等的概率就是 (pq+(1-p)(1-q)) 。对于第二类询问也是一样的，分区间覆盖 (l-1) 点和 (r) 点、覆盖其中一个点、都不覆盖三种情况考虑。代码中有切了这一档分，方便和正解对照。
我们可以同时维护住所有答案，然后只接回答询问。用一个一维数据结构维护每个点 (x) 的前缀或者后缀是否相等，一个二维数据结构用来维护 (a[x],a[y]) 的值是否相等。修改和上面的暴力是同理的，是对一个区间（一维或二维）的点附上一个修改后相等的概率，对于修改显然是交换结合都没什么关系。那这个一维数据结构选择线段树，二维数据结构选择线段树套线段树即可。
二维线段树比较好写的写法是静点套动点，不过动点套动点也可以写的。而且这道题其实空间是不够的，但比较难卡，一般卡不满。
代码
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int P=998244353;
const int N=1e5+5;
int op[N],ql[N],qr[N];
int n,m;
void exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x),y-=a/b*x;
}
int inv(int a)
{
int x,y;
exgcd(a,P,x,y);
return (x%P+P)%P;
}
namespace Subtask1
{
int merge(int x,int y)
{
return ((1ll*x*y+1ll*(1-x)*(1-y))%P+P)%P;
}
void Solve()
{
FOR(i,1,m)if(op[i]==2)
{
int l=ql[i],r=qr[i];
int p=1;
if(l==1)
{
FOR(j,1,i-1)if(op[j]==1)
{
int len=qr[j]-ql[j]+1;
if(ql[j]<=r&&r<=qr[j])
p=merge(p,inv(len));
else p=merge(p,0);
}
}
else
{
l--;
FOR(j,1,i-1)if(op[j]==1)
{
int len=qr[j]-ql[j]+1;
if(ql[j]<=l&&r<=qr[j])
p=merge(p,1ll*(len-2)*inv(len)%P);
else if((ql[j]<=l&&l<=qr[j])||(ql[j]<=r&&r<=qr[j]))
p=merge(p,1ll*(len-1)*inv(len)%P);
}
}
printf("%d
",p);
}
}
};
namespace Subtask2
{
int merge(int x,int y)
{
return ((1ll*x*y+1ll*(1-x)*(1-y))%P+P)%P;
}
struct SegmentTree
{
int pw[N<<2];
void build(int k,int l,int r)
{
pw[k]=1;
if(l==r)return;
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(int k,int L,int R,int val,int l,int r)
{
if(L<=l&&r<=R)
{
pw[k]=merge(pw[k],val);
return;
}
int mid=(l+r)>>1;
if(L<=mid)update(k<<1,L,R,val,l,mid);
if(R>mid)update(k<<1|1,L,R,val,mid+1,r);
}
int query(int k,int x,int l,int r)
{
if(l==r)return pw[k];
int mid=(l+r)>>1;
if(x<=mid)return merge(pw[k],query(k<<1,x,l,mid));
else return merge(pw[k],query(k<<1|1,x,mid+1,r));
}
};
struct SegmentTree2D
{
int lson[N*450],rson[N*450],pw[N*450];
int rt[N<<2],tot;
void build()
{
memset(rt,0,sizeof(rt));
tot=0;
}
void create(int &k)
{
k=++tot;
lson[k]=rson[k]=0;
pw[k]=1;
}
void update(int &k,int L,int R,int val,int l,int r)
{
if(!k)create(k);
if(L<=l&&r<=R)
{
pw[k]=merge(pw[k],val);
return;
}
int mid=(l+r)>>1;
if(L<=mid)update(lson[k],L,R,val,l,mid);
if(R>mid)update(rson[k],L,R,val,mid+1,r);
}
int query(int k,int x,int l,int r)
{
if(!k)return 1;
if(l==r)return pw[k];
int mid=(l+r)>>1;
if(x<=mid)return merge(pw[k],query(lson[k],x,l,mid));
else return merge(pw[k],query(rson[k],x,mid+1,r));
}
void Update(int k,int U,int D,int L,int R,int val,int u,int d,int l,int r)
{
if(U<=u&&d<=D)
{
update(rt[k],L,R,val,l,r);
return;
}
int mid=(u+d)>>1;
if(U<=mid)Update(k<<1,U,D,L,R,val,u,mid,l,r);
if(D>mid)Update(k<<1|1,U,D,L,R,val,mid+1,d,l,r);
}
int Query(int k,int x,int y,int u,int d,int l,int r)
{
if(u==d)return query(rt[k],y,l,r);
int mid=(u+d)>>1;
if(x<=mid)return merge(query(rt[k],y,l,r),Query(k<<1,x,y,u,mid,l,r));
else return merge(query(rt[k],y,l,r),Query(k<<1|1,x,y,mid+1,d,l,r));
}
};
SegmentTree ST;
SegmentTree2D ST2;
void Solve()
{
ST.build(1,1,n);
ST2.build();
FOR(i,1,m)
{
if(op[i]==1)
{
int len=qr[i]-ql[i]+1;
ST.update(1,ql[i],qr[i],inv(len),1,n);
if(ql[i]>1)ST.update(1,1,ql[i]-1,0,1,n);
if(qr[i]<n)ST.update(1,qr[i]+1,n,0,1,n);
ST2.Update(1,ql[i],qr[i],ql[i],qr[i],1ll*(len-2)*inv(len)%P,1,n,1,n);
if(ql[i]>1)ST2.Update(1,1,ql[i]-1,ql[i],qr[i],1ll*(len-1)*inv(len)%P,1,n,1,n);
if(qr[i]<n)ST2.Update(1,ql[i],qr[i],qr[i]+1,n,1ll*(len-1)*inv(len)%P,1,n,1,n);
}
else if(op[i]==2)
{
if(ql[i]==1)printf("%d
",ST.query(1,qr[i],1,n));
else printf("%d
",ST2.Query(1,ql[i]-1,qr[i],1,n,1,n));
}
}
}
};
int main()
{
scanf("%d%d",&n,&m);
FOR(i,1,m)scanf("%d%d%d",&op[i],&ql[i],&qr[i]);
if(n<=3000&&m<=3000)
{
Subtask1::Solve();
return 0;
}
Subtask2::Solve();
return 0;
}