首页 > 代码库 > Zjoi2017树状数组
Zjoi2017树状数组
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 的区间要覆盖一个点的话有 1/p 的几率，我们考虑维护一个东西使被覆盖奇偶次的概率分开
就可以构造出 pi{(i = p1 - > pn | p为覆盖了这个点的区间长度) (p-1)/p - 1/p}
我们发现将 pi 打开后里面每一项都对应一种合法覆盖方案，并且值就是那个概率。而覆盖奇数次的话，因为只有奇数个(-1/p)，所以贡献是负的
如果设x0为这个点覆盖偶数次的概率，x1为奇数次，那么上式的结果就是 x0 - x1。
而我们显然有 x0 + x1 = 1，所以就可以线段树维护一个区间乘法来维护这个概率。
但是还有些问题，如果一个修改区间同时覆盖了查询的两个点的话，这个区间的贡献会算重
那么我们要解决这个问题可以发现算重的区间要完全覆盖询问区间，所以如果把区间按(l,r)画在一个二维平面上的话，算重的区间是在询问区间的左上角的
那么这个东西可以用树状数组套主席树前缀维护，只用维护 (p-1)/p - 1/p 的逆元的乘积和一个与前面类似的概率计算式即可。
一定注意判断 (l == 1) 的情况
代码 ：
/* Lelouch vi Britannia here commands you , all of you , die ! */ #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define low(x) ((x)&(-(x))) #define LL long long #define eps 1e-9 #define MOD 998244353 using namespace std; #define int LL inline int Max(int a,int b) {return a>b?a:b;} inline int Min(int a,int b) {return a<b?a:b;} inline int Abs(int a) {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. */
Zjoi2017树状数组