【loj - 2251】「ZJOI2017」树状数组

标签：二进制   调用   内容   unsigned   printf   很多   没有   现在   clu   

description

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

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

• \(1\ x\)，表示将 \(A_x\) 变成 \((A_x + 1)\mod 2\)。
• \(2\ l\ r\)，表示询问 \((\sum_{i=l}^rA_i)\mod 2\)。

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

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

如果你对树状数组比较熟悉，不难发现可怜把树状数组写错了：\({\rm Add}\) 和 \({\rm Find}\) 中 \(x\) 变化的方向反了。因此这个程序在最终测试时华丽的爆 0 了。

然而奇怪的是，在当时，这个程序通过了出题人给出的大样例——这也是可怜没有进行对拍的原因。

现在，可怜想要算一下，这个程序回答对每一个询问的概率是多少，这样她就可以再次的感受到自己是一个多么非的人了。然而时间已经过去了很多年，即使是可怜也没有办法完全回忆起当时的大样例。幸运的是，她回忆起了大部分内容，唯一遗忘的是每一次第一类操作的 \(x\) 的值，因此她假定这次操作的 \(x\) 是在 \([l_i, r_i]\) 范围内等概率随机的。

具体来说，可怜给出了一个长度为 \(n\) 的数组 \(A\)，初始为 \(0\)，接下来进行了 \(m\) 次操作：

• \(1\ l\ r\)，表示在区间 \([l, r]\) 中等概率选取一个 \(x\) 并执行 \({\rm Add}(x)\)。
• \(2\ l\ r\)，表示询问执行 \({\rm Query}(l, r)\) 得到的结果是正确的概率是多少。

原题传送门。

solution

根据正常的树状数组推导可得：当 \(x\leq y\)，\({\rm Add}(y)\) 会对 \({\rm Find}(x)\) 产生贡献。

也就是说其实 \({\rm Find}(x)\) 是后缀和。不过这里有个坑：\({\rm Find}(0) = 0\) 恒成立。

当 \(l \not = 1\) 时，等价于询问 \(A_{l-1}= A_r\) 成立的概率。
当 \(l = 1\) 时，等价于询问 \(A_r = cnt\) 成立的概率（其中 \(cnt\) 是当前的修改次数）。

虽然到这一步可以直接用树套树维护，不过由于我人傻，所以推了个公式：

记 \(p_i\) 表示第 \(i\) 次操作使得等式状态变化的概率。则 \(\prod[p_ix+(1-p_i)]\) 的偶数项之和就是答案。

考虑代入二次单位根，得到答案为 \(\frac{1+\prod(1-2p_i)}{2}\)。然后就是三维数点问题。时间复杂度 \(O(n\log^2 n)\)。

【求大佬解释这个式子是否有组合意义】

accepted code

#include 
#include 
#include 
using namespace std;

const int MAXN = 100000;
const int MOD = 998244353;

inline int add(int x, int y) {x += y; return x >= MOD ? x - MOD : x;}
inline int sub(int x, int y) {x -= y; return x v[3][MAXN + 5];

int n, m;
inline int lowbit(int x) {return x & (-x);}
void add(int o, int x, int p, int k) {
	for(int i=x;i> 1;
	if( p > 1;
	return mul(prod(ch[0][x], l, mid, ql, qr), prod(ch[1][x], mid + 1, r, ql, qr));
}

int ans[MAXN + 5];
int main() {
	init(), scanf("%d%d", &n, &m);
	
	int qcnt = 0, nw = 0;
	for(int i=1,op,l,r;i

details

l = 1 的答案要特判也太坑了吧。不特判直接暴零。

【loj - 2251】「ZJOI2017」树状数组

标签：二进制   调用   内容   unsigned   printf   很多   没有   现在   clu   

原文地址：https://www.cnblogs.com/Tiw-Air-OAO/p/13126466.html