「POI2011 R1」棒棒糖 Lollipop 题解

问题分析

我们有一个长度为 n 的字符串，由字符 'T'（价值 2）和 'W'（价值 1）组成。对于每个询问 k，我们需要判断是否存在一个连续子串，其价值总和恰好为 k，如果存在则输出任意一个满足条件的区间 [l, r]。

关键观察

前缀和性质：设 ps[i] 表示前 i 个元素的价值和，则区间 [l, r] 的价值为 ps[r] - ps[l-1]。

特殊值判断：总价值和 total = ps[n]。如果 k > total 或 k < 1，显然无解。

奇偶性约束：由于每个元素的价值为 1 或 2，所以任意区间的价值和只能是：

如果区间中所有元素都是 'W'（价值 1），则价值和为区间长度

如果区间中包含 'T'（价值 2），则价值和可能为奇数或偶数

解题思路

思路一：直接前缀和（不可行） 最简单的想法是为每个 k 寻找是否存在 l, r 使得 ps[r] - ps[l-1] = k。但直接枚举所有区间是 O(n²) 的，对于 n 最大 10⁶ 不可行。

思路二：双指针/滑动窗口（可行但需要优化） 我们可以使用双指针法维护当前区间的价值和，但需要为每个 k 重新搜索，总复杂度 O(n·m)，仍然不可行。

思路三：预处理所有可能区间（标准解法） 核心思路：我们只需要找到对于每个可能的 k，至少一个区间端点即可。

具体算法：

计算前缀和数组：

text ps[i] = 前i个元素的价值总和 ps[0] = 0 建立值到位置的映射： 使用两个数组 first[k] 和 last[k]，分别记录价值和为 k 的前缀和第一次和最后一次出现的位置。

关键观察： 如果我们想找到一个区间和为 k，可以转化为寻找两个前缀和 ps[r] 和 ps[l-1]，使得 ps[r] - ps[l-1] = k，即 ps[r] = ps[l-1] + k。

特殊情况处理：

如果 k 是奇数，并且所有元素都是 'W'（价值 1），则无解

如果 k 大于总价值 total，无解

巧妙构造： 实际实现中，我们可以先找到总和为 total 的整个区间 [1, n]，然后：

如果左端是 'W'（价值 1），则去掉它得到区间和为 total-1

如果右端是 'W'，则去掉它得到区间和为 total-1

如果左右都是 'T'（价值 2），则去掉左端的 'T' 得到区间和为 total-2，再考虑其他情况

算法步骤

预处理：

计算总价值 total

找到第一个 'W' 和最后一个 'W' 的位置

对于每个询问 k：

如果 k > total：输出 NIE

如果 k 是奇数且所有元素都是 'W'：需要特殊处理

否则：

如果存在区间和为 k，构造这样的区间

否则输出 NIE

时间复杂度

预处理：O(n)

每个查询：O(1)

总复杂度：O(n + m)，可以通过 n, m ≤ 10⁶ 的数据

空间复杂度

O(n) 用于存储字符串和前/后缀信息

O(1) 额外空间