AC. 梦想

frank_c1

[ZJOI 2017] 树状数组

发布于2017年03月25日 | 暂无评论 | 679阅读 | 动态规划,树状数组,线段树

题意简述

有一个人在写树状数组题,模2意义。

题目需要支持单点加,求区间和。

写的时候把所有x的变化方向都写反了。

现在你需要执行两种操作:

1 l r : 在[l, r]中等概率随机一点x执行单点加。

2 l r : 询问在此时调用错误的代码求答案有多大的概率出错。

输出概率时要求对998244353取模。

1 \le n, m \le 10 ^ 5, 1 \le l \le r \le n

算法讨论

补题时发现真是清真题,可能亏了一个亿啊??

不过反正我考场上也没时间写,还是自己太菜啊。

首先找一发规律可以知道错误写法求出来的就是后缀和。

由于这里是模2意义,那么加法就等价于异或操作。

假设原来调用sum(x)操作求出来的答案是s_x,区间[l, r]的答案是s_r \oplus s_{l-1}

现在错误的sum(x)求出来的就是s_x \oplus A_x \oplus T,区间[l, r]的答案就是s_r \oplus s_{l-1} \oplus A_{l-1} \oplus A_r,注意这个结论在l \neq 1才成立,l = 1时求出来的是s_r \oplus s_{l-1} \oplus A_r \oplus T,其中T是现在所有A_i的异或和,即当前1操作的总数的奇偶性。

所以我们现在就知道了,原答案和新答案的异或在l = 1时是T \oplus A_r,在l \neq 1时是A_{l-1} \oplus A_r。这样就可以把问题规模降成单点,暴力DP就是O(q ^ 2)啦。

我们发现DP的过程满足结合律和交换律,而且和询问有关的量只有询问点和修改点的关系,分别对应了四种转移。而且我们发现四种转移的范围分别是一个矩形。于是修改时我们就在二维线段树直接打标记,查询时就是一个清真的单点查询啦。

时间复杂度O(m \log ^ 2 n)