2.1 题目描述

漆黑的晚上，九条可怜躺在床上辗转反侧。难以入眠的她想起了若干年前她的一次悲惨的 OI 比赛经历。那是一道基础的树状数组题。

给出一个长度为 n 的数组 A，初始值都为 0，接下来进行 m 次操作，操作有两种：

• 1 x，表示将 Ax 变成 (Ax + 1) mod 2。

• 2 l r，表示询问 ( ∑r i=l Ai) mod 2。

尽管那个时候的可怜非常的 simple，但是她还是发现这题可以用树状数组做。

当时非常 young 的她写了如下的算法：

1: function Add(x)

2: while x > 0 do

3: Ax ← (Ax + 1) mod 2

4: x ← x − lowbit(x)

5: end while

6: end function

7:

8: function Find(x)

9: if x == 0 then

10: return 0

11: end if

12: ans ← 0

13: while x ≤ n do

14: ans ← (ans + Ax) mod 2

15: x ← x + lowbit(x)

16: end while

17: return ans

18: end function

19:

20: function Query(l, r)

21: ansl ← Find(l − 1)

22: ansr ← Find(r)

23: return (ansr − ansl + 2) mod 2

24: end function

其中 lowbit(x) 表示数字 x 最վ的非 0 二进制位，例如 lowbit(5) = 1, lowbit(12) = 4。进 行第一类操作的时候就调用 Add(x)，第二类操作的时候答案就是 Query(l, r)。

如果你对树状数组比较熟悉，不难发现可怜把树状数组写错了：Add ， Find 中 x 变化 的方向反了。因此这个程序在最终测试时华丽的爆 0 了。 然而奇怪的是，在当时，这个程序通过了出题人给出的大样例——这也是可怜没有进行对 拍的原因。

现在，可怜想要算一下，这个程序回答对每一个询问的概率是多少，这样她就可以再次的 感受到自己是一个多么非的人了。然而时间已经过去了很多年，即使是可怜也没有办法完全回 忆起当时的大样例。

幸运的是，她回忆起了大部分内容，唯一遗忘的是每一次第一类操作的 x 的值，因此她假定这次操作的 x 是在 [li , ri ] 范围内 等概率 的。 具体来说，可怜给出了一个长度为 n 的数组 A，初始为 0，接下来进行了 m 次操作：

• 1 l r，表示在区间 [l, r] 中等概率选取一个 x 并执行 Add(x)。

• 2 l r，表示询问执行 Query(l, r) 得到的结果是正确的概率是多少。

2.2 输入格式

第一行输入两个整数 n, m。 接下来 m 行每行描述一个操作，格式如题目中所示。

2.3 输出格式

对于每组询问，输出一个整数表示答案。如果答案化为最简分数后形如 x y，那么你只需要 输出 x × y −1 mod 998244353 后的值。（即输出答案模 998244353）。

--------------------------------------------------此后一千里-----------------------------------------------------------

 

 

 

 

 

 

 

 

 

 

 

 

 

可以比较显然地发现树状数组写反之后，实际上是由原来的统计前缀变成了统计后缀。

那么唯一的问题就是计算答案时依然是用的 q(r) - q(l - 1)，而正确的应该是 q(l) - q(r + 1)。

那么对答案有影响的话，就只有修改在 r 和 l - 1这两个位置才会影响答案，而我们只在意奇偶性，所以问题就变成了求修改了 r 和 l - 1偶数次的概率

那么我们可以去求每个点被修改了偶数次的概率来解决问题

发现一个长度为 $p_i$ 的区间要覆盖一个点的话有 $\frac{1}{p_i}$ 的几率，我们考虑维护一个东西使被覆盖奇偶次的概率分开

设覆盖点$x$的所有区间集合为$S_x$就可以构造出 $\prod \limits_{i \in S_x} (\frac{p_i-1}{p} - \frac{1}{p})$

我们发现将 pi 打开后里面每一项都对应一种合法覆盖方案，并且值就是那个概率。而覆盖奇数次的话，因为只有奇数个(-1/p)，所以贡献是负的

如果设x0为这个点覆盖偶数次的概率，x1为奇数次，那么上式的结果就是 x0 - x1。

而我们显然有 x0 + x1 = 1，所以就可以线段树维护一个区间乘法来维护这个概率。

但是还有些问题，如果一个修改区间同时覆盖了查询的两个点的话，这个区间的贡献会算重

那么我们要解决这个问题可以发现算重的区间要完全覆盖询问区间，所以如果把区间按(l,r)画在一个二维平面上的话，算重的区间是在询问区间的左上角的

那么这个东西可以用树状数组套主席树前缀维护，只用维护 $\frac{p_i-1}{p} - \frac{1}{p}$ 的逆元的乘积和一个与前面类似的概率计算式即可。

一定注意判断 (l == 1) 的情况

upd: 总有感觉对于区间同时覆盖两个点的情况有一种优雅的解决方式，从而使时间复杂度达到O(nlogn)，然而并想不出。

代码 ：

/*Lelouch vi Britannia here commands you , all of you , die !*/#include
      
       #define INF 0x3f3f3f3f#define low(x) ((x)&(-(x)))#define LL long long#define eps 1e-9#define MOD 998244353using namespace std; #define int LLinline int Max(int a,int b) {
    return a>b?a:b;}inline int Min(int a,int b) {
    return a
       
        0?a:-a;}inline int Sqr(int a) {
    return a*a;}#undef int #define MAXN 100005 namespace SegmentTree{    struct Node{        int mul;    }x[MAXN*4];         void Build(int l,int r,int num) {        x[num].mul=1;        if(l==r) return;        int mid=l+r>>1;        Build(l,mid,num<<1);        Build(mid+1,r,num<<1|1);    }    void Mult(int nl,int nr,int l,int r,int num,LL d) {        if(l==nl&&r==nr) {x[num].mul=(LL) x[num].mul*d%MOD;return;}        int mid=l+r>>1;        if(nl>mid) Mult(nl,nr,mid+1,r,num<<1|1,d);        else if(nr<=mid) Mult(nl,nr,l,mid,num<<1,d);        else {            Mult(mid+1,nr,mid+1,r,num<<1|1,d);            Mult(nl,mid,l,mid,num<<1,d);        }    }    LL Query(int l,int r,int num,int p) {        if(!p) return 1;        if(l==r) return x[num].mul;        int mid=l+r>>1;LL ret;        if(p<=mid) ret=Query(l,mid,num<<1,p);        else ret=Query(mid+1,r,num<<1|1,p);        return ret*x[num].mul%MOD;    }}struct Pa{    int x,y;    Pa () {}    Pa (int _,int __) : x(_),y(__) {}    Pa operator * (const Pa b) {        Pa ret=b;        ret.x=(LL) ret.x*x%MOD;        ret.y=(LL) ret.y*y%MOD;        return ret;    }};const int L=0,R=1;struct Node{    int son[2];    Pa val;}x[MAXN*300];int sz,root[MAXN];struct ChiarmanTree{    void Updata(int num) {        int ls=x[num].son[L],rs=x[num].son[R];        x[num].val=x[ls].val*x[rs].val;    }         void Insert(int l,int r,int fr,int &now,int p,Pa d) {        if(!now) {now=++sz;x[now]=x[fr];x[now].val=Pa(1,1);}        if(l==r) {x[now].val=x[now].val*d;return;}        int mid=l+r>>1;        if(p>mid) Insert(mid+1,r,x[fr].son[R],x[now].son[R],p,d);        else Insert(l,mid,x[fr].son[L],x[now].son[L],p,d);        Updata(now);    }    Pa Query(int l,int r,int num,int p) {        if(l==r) return x[num].val;        int mid=l+r>>1;        if(p>mid) return Query(mid+1,r,x[num].son[R],p);        else return Query(l,mid,x[num].son[L],p)*x[x[num].son[R]].val;    }}ct[MAXN]; #define SGT SegmentTree int n,m;LL ni[MAXN]; LL Fpow(LL a,LL p) {    LL tmp=a,ret=1;    while(p) {        if(p&1) ret=ret*tmp%MOD;        p>>=1; tmp=tmp*tmp%MOD;    }    return ret;} void Pre(int n) {    ni[1]=1;    for(int i=2;i<=n;i++)         ni[i]=(MOD-MOD/i)*ni[MOD%i]%MOD;} void Insert(int x,int y,int d,int t) {    for(int i=x;i<=n;i+=low(i))         ct[x].Insert(1,n,root[i],root[i],y,Pa(d,t));}Pa Query(int x,int y) {    Pa ret(1,1);    for(int i=x;i;i-=low(i))         ret=ret*ct[x].Query(1,n,root[i],y);    return ret;} struct Query{    int l,r,cat,id;    LL p1,p2,p3;         LL Calc() {        LL ret=0,p10,p20,p30;        p10=(1+p1)*ni[2]%MOD;        p20=(1+p2)*ni[2]%MOD;        p30=(1+p3)*ni[2]%MOD;        ret=(ret+p10*p20%MOD*p30%MOD)%MOD;        ret=(MOD+ret+p10*(1-p20)%MOD*(1-p30)%MOD)%MOD;        ret=(MOD+ret+p20*(1-p10)%MOD*(1-p30)%MOD)%MOD;        ret=(MOD+ret+p30*(1-p20)%MOD*(1-p10)%MOD)%MOD;        return ret;    }}q[MAXN]; int main() {    scanf("%d%d",&n,&m);    Pre(n);SGT:: Build(1,n,1);x[0].val=Pa(1,1);    for(int cat,i=1;i<=m;i++) {        scanf("%d%d%d",&q[i].cat,&q[i].l,&q[i].r);        int len=q[i].r-q[i].l+1;q[i].id=i;        if(q[i].cat==1) SGT:: Mult(q[i].l,q[i].r,1,n,1,(MOD+len-2)*ni[len]%MOD);        else {            LL ans1,ans2,p1,p2;            p1=SGT:: Query(1,n,1,q[i].l-1);p2=SGT:: Query(1,n,1,q[i].r);            q[i].l--;q[i].p1=p1;q[i].p2=p2;q[i].p3=1;        }    }    for(int cnt=0,i=1;i<=m;i++) {        if(q[i].cat==1) {            cnt++;            int len=q[i].r-q[i].l+1;            int mu=Fpow((MOD+len-2)*ni[len]%MOD,MOD-2);            Insert(q[i].l,q[i].r,mu,(MOD+len-4)%MOD*ni[len]%MOD);        }        else {            Pa mu=Query(q[i].l,q[i].r);            q[i].p1=q[i].p1*mu.x%MOD;            q[i].p2=q[i].p2*mu.x%MOD;            q[i].p3=mu.y;            printf("%lld\n",(cnt&1&&!q[i].l)?(MOD+1-q[i].Calc())%MOD:q[i].Calc());        }    }    return 0;}/*Hmhmhmhm . That's right , I am killer.*/