BZOJ 4785 [Zjoi2017] 树状数组

发布于 2017-12-05  220 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4785

题意:一个人的树状数组写错了,具体错在将修改操作和查询操作跳 lowbit 的顺序写反了,支持区间内随机单点取反,区间异或和查询,询问这个人的答案没错的概率。


如果熟悉树状数组或者打一下表可以简单的发现这个人写错的后果就是查询是后缀和不是前缀和了。

那么他的答案会错当且仅当 l-1 和 r 这两个位置被修改的次数在模 2 的意义下不同。将平面上的点 (l,r) 视作序列上的 l 和 r 这两个位置修改次数在模 2 意义下相同的概率。

每次修改操作分类讨论即可,实际上是三个矩形覆盖。概率可以简单合并,即分别讨论都变和都不变的情况即可,所以二维线段树可以维护这个修改。

如果只观察到这里就死定了,树状数组如果访问了 0 下标会炸,所以观察伪代码,发现访问 0 下标的时候返回了 0,不可以简单套用上述做法,单独维护下就好了。

二维线段树的话外层只需要维护上传标记即可,为了方便内层也写了标记永久化,其实没有必要。

 


一个非常弱的准退役OIER