5e5, 10s 最严厉的父亲

题意：给出一个长度为

n

的 cute 的序列

a_1, a_2, \dots, a_n

，以及

q

次询问，每次询问给出

l, r

，求

a_l, a_{l+1}, \dots, a_r

中出现次数为奇数的数之和。强制在线。

正常选手可以注意到题目给出了 cute 序列的定义。这是一个很好的性质。但是我是一个注意力涣散的人，所以我没有注意到序列

a

是 cute 的。因此这里直接给出任意序列的做法。

考虑到

n \le 5 \times 10^5

，而时限是

10\mathrm{s}

，这不禁唤起我们做 ynoi 的美好回忆，吸引这我们去触碰根号算法的禁地。

于是我们搓一个分块做法：序列按照

B=\sqrt n

分块后，预处理所有

O(\sqrt n \times \sqrt n) = O(n)

个整块区间的答案，耗时

O(n \sqrt n)

。然后对于一次查询：

若端点在同一块，直接暴力；
否则，先获取中间整块的答案（已经预处理过），然后加上两边散块的贡献。在计算贡献时还需要得知每个数在整块中出现次数的奇偶性，这里可以直接给每个数开一个前缀和来计算。但是 $O(n \sqrt n)$ 的空间会炸，所幸我们只需要储存 $0/1$ ，因此 bitset 压位解决。

可见查询的复杂度均为

O(\sqrt n)

。整个算法复杂度为

O(n \sqrt n + q \sqrt n)

。

文章操作