可以发现这个写挂的树状数组求的是后缀和。find(r)-find(l-1)在模2意义下实际上查询的是l-1~r-1的和，而本来要查询的是l~r的和。也就是说，若结果正确，则a[l-1]=a[r](mod 2)。
一个很容易想到的思路是线段树维护每一位为1的概率。然而这其实是不对的，因为每一位是否为1并非独立事件。
世界上没有什么事情是用一维线段树解决不了的，如果有，那就两维
我们维护每两位之间相同的概率。考虑一次操作对某两位的影响。若该次操作包含两位中的x位，那么改变两者间相同状态的概率就是x/len，len为该次修改的区间长度。设原相同概率为pi,j，那么操作后概率就变为(1-pi,j)*x/len+pi,j*(1-x/len)。这个式子神奇的满足交换律结合律，算的时候我们就不用管顺序了。
用二维线段树就可以维护了。修改时先拆成外层线段树上的区间再在内层线段树修改，查询时将所有外层区间包含该点的内层线段树上的操作合在一起。并且需要标记永久化。
注意l=1时find(l-1)直接返回0而不是整个数组的和，此时询问的是r后缀和r前缀是否相等，需要特判一下，记录修改了几次以及r这一位为0的概率（即和第0位相同的概率）。
（写起来出乎意料的短
（空间需要开的非常大
（当然也可以cdq分治变成静态数点扫描线扫过去就好了
#include#include #include #include #include #include using namespace std;int read(){ int 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<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 100010#define P 998244353int n,m,tot=0,inv[N],L[N<<2],R[N<<2],cnt=0;int root[N<<2];struct data{ int l,r,x;}tree[N*400];void inc(int &x,int y){x+=y;if (x>=P) x-=P;}int calc(int x,int y){ return (1ll*x*(P+1-y)+1ll*y*(P+1-x))%P;}void build(int k,int l,int r){ L[k]=l,R[k]=r; if (l==r) return; int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r);}void modify(int &k,int l,int r,int x,int y,int a){ if (!k) k=++cnt; if (l==x&&r==y) { tree[k].x=calc(tree[k].x,a); return; } int mid=l+r>>1; if (y<=mid) modify(tree[k].l,l,mid,x,y,a); else if (x>mid) modify(tree[k].r,mid+1,r,x,y,a); else modify(tree[k].l,l,mid,x,mid,a),modify(tree[k].r,mid+1,r,mid+1,y,a);}int query(int k,int l,int r,int x,int ans){ if (!k) return ans; ans=calc(ans,tree[k].x); if (l==r) return ans; int mid=l+r>>1; if (x<=mid) return query(tree[k].l,l,mid,x,ans); else return query(tree[k].r,mid+1,r,x,ans);} void change(int k,int l,int r,int x,int y,int a){ if (L[k]==l&&R[k]==r) {modify(root[k],0,n,x,y,a);return;} int mid=L[k]+R[k]>>1; if (r<=mid) change(k<<1,l,r,x,y,a); else if (l>mid) change(k<<1|1,l,r,x,y,a); else change(k<<1,l,mid,x,y,a),change(k<<1|1,mid+1,r,x,y,a);}int getans(int x,int y){ int k=1,s=1; while (1) { s=calc(s,query(root[k],0,n,y,0)); if (L[k]==R[k]) break; if (x<=(L[k]+R[k]>>1)) k<<=1; else k=k<<1|1; } return s%P;}int main(){#ifndef ONLINE_JUDGE freopen("bzoj4785.in","r",stdin); freopen("bzoj4785.out","w",stdout); const char LL[]="%I64d";#else const char LL[]="%lld";#endif n=read(),m=read(); inv[1]=1; for (int i=2;i<=n;i++) inv[i]=(P-1ll*(P/i)*inv[P%i]%P)%P; build(1,0,n); for (int i=1;i<=m;i++) { int op=read(),l=read(),r=read(); if (op==1) { tot^=1;int x=inv[r-l+1]; change(1,0,l-1,l,r,x); if (r