SCCPC2026 G 禁忌教典的消失咒文 题解

题目链接：QOJ Contest 3789 Problem G

我们要删除一个非空连续区间，然后把剩下的两段拼起来。麻烦的地方在于，拼接以后右半段的符号可能会改变。

定义交替前缀和

设删除区间是 ，令

也就是说，我们要统计 的二元组。

删除 后，前半段 的符号不变；后半段 是否翻转，取决于删除长度 的奇偶性。

如果 是偶数，右半段的符号不变，删除后的能量为

要求它等于 ，即

这时 同奇偶。

如果 是奇数，右半段的符号会翻转，删除后的能量为

要求它等于 ，即

这时 异奇偶。

于是可以从左到右枚举右端点 ，用两个哈希表维护此前出现过的 ：一个存偶数下标，一个存奇数下标。

对于当前 ：

• 同奇偶情况需要找 ；
• 异奇偶情况需要找 。

把两类方案数加入答案后，再把当前的 放入对应奇偶性的哈希表。

注意删除区间要求非空，而我们始终枚举 ，所以不会把空区间算进去。

使用哈希表时，时间复杂度为期望 ，空间复杂度为 。如果使用平衡树或 map，时间复杂度为 。