点我传送到题目喵

思路分析

遇到环形的结构，我们考虑将问题转化为线性：将原数组复制一份，得到长度为 $2n$ 的序列 $b$。对于每个可能的旋转起点 $s$（$0 \le s < n$），旋转后的序列即为 $b_s, b_{s+1}, \dots, b_{s+n-1}$。我们需要统计这个序列中前缀严格最大值的个数，并求出最大值。

对于 $b$ 中的每个位置 $j$（$0 \le j < 2n$），考虑它成为旋转后序列中一个“记录”的条件。设 $l_j$ 为 $j$ 左边第一个满足 $b_{l_j} \ge b_j$ 的位置（若不存在则为 $-1$）。那么对于旋转起点 $s$，当且仅当 $s \le j < s+n$（即 $j$ 在旋转后的区间内）且 $l_j < s$（即从 $s$ 到 $j-1$ 之间没有大于等于 $b_j$ 的数，因此 $b_j$ 是当前最大值）时，$b_j$ 会成为新的记录。

因此，每个 $j$ 会对所有满足 $s \in [\max(l_j+1,\ j-n+1),\ \min(j,\ n-1)]$ 的 $s$ 贡献一次。我们只需要对每个 $s$ 统计有多少 $j$ 的区间覆盖了 $s$，然后取最大值即可。

由此我们可以解决本题：

• 将原数组复制一倍，得到数组 $b$。

• 使用单调栈（维护非递增序列）计算每个 $j$ 的 $l_j$。

• 建立差分数组 $c$（长度为 $n+2$），对于每个 $j$：

  • 计算左端点 $l = \max(l_j+1,\ j-n+1)$，右端点 $r = \min(j,\ n-1)$。

  • 若 $l \le r$，则 $c_{l} \leftarrow c_{l}+1$，$c_{r+1} \leftarrow c_{r+1}-1$。

• 遍历从 $0$ 到 $n-1$ 的每个 $s$，累加差分值 $cnt$，更新答案 $ans = \max(ans, cur)$。最后输出即可。

复杂度

时间：$O(n)$，单调栈和差分均为线性。

空间：$O(n)$。