两个关于子段和的题

前几天和同事聊天，聊到前几天的北京数学高考题。最后一个题还挺有意思的，我和同事 yy 了好久都不会：

给定两个序列 \(\{a_i\}, \{b_i\} \in [n]^n\)，证明存在四个正整数 \(l_a \leq r_a, l_b \leq r_b\) 使得 \[\sum_{i=l_a}^{r_a} a_i = \sum_{i = l_b}^{r_b} b_i.\]

在想这个题的时候，我想到了曾经做 POI 的时候见过的一个题：

给定一个大小为 \(n\) 的序列 \(a\)，其中 \(a_i \in \{1, 2\}\)。

现在有 \(m\) 个询问，每次给定一个 \(k\)，要你找出一个和为 \(k\) 的子段，或者输出不存在。

数据范围为 \(n \leq 10^7, k \leq 10^5\)。

高考题

定义 \(A_t = \sum\limits_{i=1}^t a_i\) 为 \(a\) 的前缀和，\(B_t\) 为 \(b\) 的前缀和。原题有一个提示：不妨令 \(A_n \leq B_n\)，定义 \(r_i = \min \{0 \leq j \leq n: A_i \leq B_j\}\)。考虑 \(d_i = B_{r_i} - A_i\)，注意到当 \(r_i > 0\) 时有 \[ B_{r_i - 1} < A_i \leq B_{r_i}, \] 故有 \(d_i < B_{r_i} - B_{r_i - 1} \leq n\)，而 \(r_i = 0\) 意味着 \(A_i = 0\)，所以 \(i = 0\)，而我们又有 \(d_0 = 0\)，综上有： \[ \forall 0 \leq i \leq n, \quad 0 \leq d_i < n. \] 由于我们有 \(n + 1\) 个 \(d_i\)，但是不同的 \(d_i\) 只有 \(n\) 个，所以必定存在 \(d_i = d_j\)，这也就意味着 \[ B_{r_i} - A_i = B_{r_j} - A_j, \] 证毕。

POI

我看到这个题的第一反应是 FFT，但是 FFT 有三个缺点：

• 难写；
• 慢，这里 \(n\) 的范围是 \(10^7\)，FFT 估计太慢了；
• 最重要的一点，FFT 没法输出位置……

后来实在不会只好去看 tutorial，发现就一句话的事：

如果存在一个和为 \(k\) 的子段且 \(k > 2\)，那么必定存在一个和为 \(k - 2\) 的子段。

证明很简单，假设 \([i, j]\) 的子段和为 \(k\)，我们考虑 \(a_i\) 和 \(a_j\)：

• 如果 \(a_i = 2\)，那么 \([i + 1, j]\) 满足要求；
• 如果 \(a_j = 2\)，那么 \([i, j - 1]\) 满足要求；
• 否则必定有 \(a_i = a_j = 1\)，那么 \([i + 1, j - 1]\) 满足要求。

于是，我们只要找到最大的和为奇数的子段和最大的和为偶数的子段即可。全序列肯定是其中一个，另一个就看第一个 1 和最后一个 1 出现的位置就可以了。