bzoj4785 [Zjoi2017]树状数组

Description

漆黑的晚上，九条可怜躺在床上辗转反侧。难以入眠的她想起了若干年前她的一次悲惨的OI 比赛经历。那是一道基础的树状数组题。给出一个长度为 n 的数组 A，初始值都为 0，接下来进行 m 次操作，操作有两种：

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

2 l r，表示询问 sigma(Ai) mod 2,L<=i<=r

尽管那个时候的可怜非常的 simple，但是她还是发现这题可以用树状数组做。当时非常young 的她写了如下的算法：

1: function Add(x)

2: while x > 0 do

3: A

x ← (Ax + 1) mod 2

4: x ← x ? lowbit(x)

5: end while

6: end function

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) 得到的结果是正确的概率是多少。

Input

第一行输入两个整数 n, m。

接下来 m 行每行描述一个操作，格式如题目中所示。

N<=10^5,m<=10^5,1<=L<=R<=N

Output

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

Sample Input

5 5
1 3 3
2 3 5
2 4 5
1 1 3
2 2 5

Sample Output

1
0
665496236
在进行完 Add(3) 之后， A 数组变成了 [0, 1, 1, 0, 0]。所以前两次询问可怜的程序答案都是1，因此第一次询问可怜一定正确，第二次询问可怜一定错误。

正解：树套树（二维线段树）。

这道题好绕。。其实如果你打表，或者是深知树状数组的原理的话，你就可以发现，询问的时候其实是查询后缀和。

那么对于每个询问，如果$l!=1$，那么我们查询的其实是$[l-1,r-1]$这段区间。而$[l-1,r-1]$与$[l,r]$仅有$l-1$和$r$这两个元素有区别。所以我们每次询问就是问$l-1$和$r$的修改次数在模2意义下是否相等。

那么我们可以把每个询问看成$(l-1,r)$这个点，那么这就是个二维选点问题了，我们用树套树来维护。外层的树维护第一维坐标，内层的树维护第二维坐标。我们维护的值就是这个点的两个坐标修改次数在模2意义下相等的概率。

如何合并概率呢？当两个点被修改的概率分别为$p1,p2$时，两个点修改次数相等的概率是$p=p1*p2+(1-p1)*(1-p2)$，这个式子也适用于合并操作。

当$l=1$时，情况类似，我们要求的就变成了对于$r$这个点，它的前缀和是否与它的后缀和相等。维护思想与$l!=1$的情况类似。

这道题的修改操作有点复杂，我在代码里加一点注释吧。。

然后我被$uoj$的$hack$数据卡常了$woc$。。

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <complex>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cstdio>
  8 #include <vector>
  9 #include <cmath>
 10 #include <queue>
 11 #include <stack>
 12 #include <map>
 13 #include <set>
 14 #define rhl (998244353)
 15 #define lson (x<<1)
 16 #define rson (x<<1|1)
 17 #define mid ((l+r)>>1)
 18 #define inf (1<<30)
 19 #define N (100010)
 20 #define il inline
 21 #define RG register
 22 #define ll long long
 23 #define merge(p1,p2) ( (p1*p2+(1-p1+rhl)*(1-p2+rhl))%rhl ) //合并操作
 24 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 25 
 26 using namespace std;
 27 
 28 int ls[330*N],rs[330*N],rt[4*N],sz; //二维线段树
 29 ll sum[330*N],ans;
 30 int n,m;
 31 
 32 il int gi(){
 33     RG int x=0,q=1; RG char ch=getchar();
 34     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
 35     if (ch=='-') q=-1,ch=getchar();
 36     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
 37     return q*x;
 38 }
 39 
 40 //求逆元
 41 il ll qpow(RG ll a,RG ll b){
 42     RG ll ans=1;
 43     while (b){
 44     if (b&1) ans=ans*a;
 45     a=a*a,b>>=1;
 46     if (ans>=rhl) ans%=rhl;
 47     if (a>=rhl) a%=rhl;
 48     }
 49     return ans;
 50 }
 51 
 52 //内层线段树修改
 53 il void update(RG int &x,RG int l,RG int r,RG int xl,RG int xr,RG ll v){
 54     if (!x) sum[x=++sz]=1;
 55     if (xl<=l && r<=xr){
 56     sum[x]=merge(sum[x],v);
 57     return;
 58     }
 59     if (xr<=mid) update(ls[x],l,mid,xl,xr,v);
 60     else if (xl>mid) update(rs[x],mid+1,r,xl,xr,v);
 61     else update(ls[x],l,mid,xl,mid,v),update(rs[x],mid+1,r,mid+1,xr,v);
 62     return;
 63 }
 64 
 65 //内层线段树查询
 66 il void query(RG int x,RG int l,RG int r,RG int p){
 67     if (!x) return; ans=merge(ans,sum[x]); if (l==r) return;
 68     p<=mid?query(ls[x],l,mid,p):query(rs[x],mid+1,r,p); return;
 69 }
 70 
 71 //外层线段树修改
 72 il void Update(RG int x,RG int l,RG int r,RG int l1,RG int r1,RG int l2,RG int r2,RG ll v){
 73     if (l1<=l && r<=r1){ update(rt[x],0,n+1,l2,r2,v); return; }
 74     if (r1<=mid) Update(lson,l,mid,l1,r1,l2,r2,v);
 75     else if (l1>mid) Update(rson,mid+1,r,l1,r1,l2,r2,v);
 76     else Update(lson,l,mid,l1,mid,l2,r2,v),Update(rson,mid+1,r,mid+1,r1,l2,r2,v);
 77     return;
 78 }
 79 
 80 //外层线段树查询
 81 il void Query(RG int x,RG int l,RG int r,RG int p1,RG int p2){
 82     if (rt[x]) query(rt[x],0,n+1,p2); if (l==r) return;
 83     p1<=mid?Query(lson,l,mid,p1,p2):Query(rson,mid+1,r,p1,p2);
 84     return;
 85 }
 86 
 87 il void work(){
 88     n=gi(),m=gi(); RG int type,l,r;
 89     for (RG int i=1;i<=m;++i){
 90     type=gi(),l=gi(),r=gi();
 91     if (type==1){
 92         RG ll p=qpow(r-l+1,rhl-2);
 93         //一个点被修改的概率为p=1/(r-l+1)
 94         //l!=1的情况
 95         if (l>1) Update(1,0,n,1,l-1,l,r,(1-p+rhl)%rhl);
 96         if (r<n) Update(1,0,n,l,r,r+1,n,(1-p+rhl)%rhl);
 97         //[1,l-1]与[l,r]和[l,r]与[r+1,n]之间,修改次数相等的概率为(1-p)
 98         RG ll pp=p<<1; if (pp>=rhl) pp-=rhl;
 99         Update(1,0,n,l,r,l,r,(1-pp+rhl)%rhl);
100         //[l+r]与[l+r]之间,修改次数相等的概率为1-2*p
101         //l==1的情况
102         Update(1,0,n,0,0,0,l-1,0);
103         Update(1,0,n,0,0,r+1,n+1,0);
104         //[0,l-1]和[r+1,n+1]这两个区间,前缀和等于后缀和的概率为0
105         Update(1,0,n,0,0,l,r,p);
106         //[l,r]这个区间,前缀和等于后缀和的概率为p
107     } else{
108         ans=1,Query(1,0,n,l-1,r);
109         //查询操作,即查询(l-1,r)修改次数相等的概率
110         //若l==1,即查询r的前缀和等于后缀和的概率
111         printf("%lld
",ans);
112     }
113     }
114     return;
115 }
116 
117 int main(){
118     File("bit");
119     work();
120     return 0;
121 }