前几天和同事聊天，聊到前几天的北京数学高考题。最后一个题还挺有意思的，我和同事 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 出现的位置就可以了。