水果序列 题解

思路

固定右端点 $r$，记 $g_l=f(l,r)$。随着 $l$ 增大，$g_l$ 单调不增。设当前结尾连续 1 的长度为 $k$，其起点为 $p$。

若新字符为 0，已有 $g_l$ 不变，并新增 $g_r=0$。若新字符为 1，对于 $l<p$ 有 $g_l\leftarrow\max(g_l,k)$；对于 $p\le l\le r$，这些子串全为 1，对应值依次为 $k,k-1,\ldots,1$。

做法

子任务 1 枚举所有子串，再线性扫描其中最长连续 1 段，复杂度 $O(n^3)$。

子任务 2 固定左端点并逐步扩展右端点，同时维护当前连续段和历史最大值，复杂度 $O(n^2)$。

满分算法用单调栈维护当前连续段以前的 $g_l$。栈中每段记录相同值及其出现次数。当前连续段长度从 $k-1$ 增至 $k$ 时，弹出栈尾所有小于 $k$ 的段并把它们合并为值 $k$；当前连续段内部的贡献为 $k(k+1)/2$。遇到 0 时，将上一连续段的 $k,k-1,\ldots,1$ 依次并入栈，再加入一个零值位置。每个位置只被加入、合并和弹出常数次。

正确性证明

对每个右端点，栈准确表示当前连续段起点以前所有 $g_l$，且按 $l$ 单调不增。加入 1 后，跨越当前连续段起点的子串只可能把最长段更新为 $k$，弹出并合并所有小于 $k$ 的栈尾恰好完成 $\max(g_l,k)$；完全位于当前连续段内的子串最长段依次为 $k$ 到 $1$。加入 0 时最长段不变，提交上一连续段并新增零值即得到全部 $g_l$。因此每轮累加的是所有以该位置为右端点的 $f(l,r)$ 之和，再对所有右端点求和即为答案。

复杂度

时间复杂度 $O(n)$，空间复杂度 $O(n)$。