题解：P11121 [ROIR 2024 Day 1] 双调序列

Forge_Unique · 2024-10-01 13:55:41 · 题解

题目描述

称一个序列 [b_1, b_2, \dots, b_k] 为双调序列（Bitonic Sequence），当且仅当存在一个 1 \leq i \leq k 使得 b_1 < b_2 < \dots < b_i > \dots > b_k 。

例如，序列 [1]，[2,4,5,7,5,4]，[1, 4, 10]，[3, 2] 都是双调序列，而序列 [1, 1]，[5,4,2,4,5,7]，[1,1,4,5,1,4] 都不是。

给定一个序列 [a_1, a_2, \dots, a_n]。要求计算满足条件的 (l, r) 对的数量，其中 1 \leq l \leq r \leq n 并且序列 [a_l, a_{l+1}, \dots, a_r] 是双调序列。

思路

定义两个数组 s_i，f_i 分别表示 a 数组中以 i 为结尾的最长上升子序列和 a 数组中以 i 为开头的最长下降子序列。根据组合数学可知，以 i 为分段处的答案就是 s_if_i。而 s_i，f_i 这两个数组可以用 O(n) 的时间复杂度递推求出来。所以总时间复杂度为 O(n) 可以通过本题。

代码

code