5e5, 10s 最严厉的父亲

ExplodingKonjac · 2025-10-11 09:22:18 · 题解

【原题链接】

题意：给出一个长度为 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)。

也是艹过去了。调一下块长可以更快。