BZOJ4785 树状数组

题目传送门

solution

写错的树状数组其实就是求一个后缀和,设suml[i]为前缀和,sumr[i]为后缀和,则题目要求suml[r]-suml[l-1],然后我们来比较一下suml[r]-sum[l-1]和-(sumr[l-1]-sumr[r])(相反数在mod 2 意义下相等)发现他们相差的就是val[l-1]和val[r],然后要使他们相等就是说val[l-1]和val[r]要在mod 2意义下相等,当l=1时就是询问一个点的前缀和和后缀和是否相等。
然后将每个询问看成一个二维平面上的点,(l-1,r),用树套树来维护点合法的概率,用(l1,r1,l2,r2)表示左端点在l1,r1间,右端点在(l2,r2)间的所有区间,然后在(l,r)区间内改一个点会影响到(1,l-1,l,r),(l,r,r+1,n),(l,r,l,r),计算两个端点这一次修改都不修改的概率。当l=1时前缀和等于后缀和的概率就是这个点被改的概率,因为它前面或后面被改了就不相等了,一次只改一个数。然后合并这些概率就得到了这个点合法的概率,设以前的概率是p1,这一次的概率是p2,合并就是$(p1p2+(1-p1)(1-p2))$就是两次都相等或都不相等,然后一合并就都相等了。
所以说问题就变成了改一个矩阵中的概率,单点询问。然后就是树套树打标记。

4 条评论
  1. I and my pals were following the great suggestions from the website then unexpectedly I got a terrible suspicion I never thanked the web site owner for those tips. My people became as a consequence thrilled to learn them and now have in truth been having fun with those things. I appreciate you for turning out to be considerably kind as well as for making a choice on this sort of useful guides millions of individuals are really wanting to know about. Our sincere apologies for not expressing appreciation to earlier.

发表一条评论