P4755

P4755 Beautiful Pair 给你一个长度为 \(n\) 的序列 \(a\)，求有多少个区间 \([l, r]\) 满足 \(a_l \cdot a_r \le \max_{i = l}^r a_i\)。 \(n \le 10^5, a_i \le 10^9\)。 首先按最大值位置分治。 ......

洛谷。 题意 显然。 分析 首先考虑到分治，那么问题就在于如何维护经过某个结点的方案数。 利用从中间结点向两端的前缀后缀最大值，接下来我们对左端点的每一个结点考虑连向右侧的方案数。 考虑分类讨论，令左端点为 \(i\)，右端点为 \(j\)。 假如 \(mx_i> mx_j\)，那么我们整个区间的最 ......