题目分析

问题本质

统计所有连续子数组 $a[i..j]$ 中，满足平均价格 $\geq P$ 的子数组个数。

关键数学转化

平均数条件转化

对于子数组 $a[i..j]$，平均价格条件为：

$$\frac{\sum_{k=i}^j a_k}{j-i+1} \geq P$$

两边乘以长度 $(j-i+1)$：

$$\sum_{k=i}^j a_k \geq P \cdot (j-i+1)$$

前缀和表示

令 $sum[k] = \sum_{t=1}^k a_t$，则：

$$sum[j] - sum[i-1] \geq P \cdot (j-i+1)$$

进一步转化

将不等式重组：

$$sum[j] - P \cdot j \geq sum[i-1] - P \cdot (i-1)$$

令 $b[k] = sum[k] - P \cdot k$，则问题转化为： 统计有多少对 $(i,j)$ 满足 $0 \leq i < j \leq N$ 且 $b[j] \geq b[i]$

问题重新表述

现在问题变成：在数组 $b[0..N]$ 中（注意 $b[0] = 0$），统计有多少个逆序对 $(i,j)$ 满足 $i < j$ 且 $b[i] \leq b[j]$。

算法框架

解法1：树状数组/线段树（推荐）

步骤1：预处理

1. 计算前缀和 $sum[i] = \sum_{k=1}^i a_k$
2. 计算 $b[i] = sum[i] - P \cdot i$，特别地 $b[0] = 0$
3. 得到数组 $b[0..N]$

步骤2：离散化 由于 $a_i$ 和 $P$ 范围很大，$b[i]$ 的值域可能很大，需要离散化：

• 将 $b[0..N]$ 排序去重，得到排名映射
• 将原值映射到 $[1, M]$ 的整数范围

步骤3：树状数组统计 从左到右扫描 $b$ 数组：

• 对于每个 $b[j]$，查询树状数组中值 $\leq b[j]$ 的元素个数
• 将 $b[j]$ 加入树状数组
• 累加所有查询结果

时间复杂度：$O(N \log N)$

解法2：归并排序求"顺序对"

思路：

• 通常归并排序用于求逆序对（$b[i] > b[j]$）
• 这里需要求"顺序对"（$b[i] \leq b[j]$）
• 在归并过程中统计左半部分 $\leq$ 右半部分的元素对

步骤：

1. 对 $b$ 数组进行归并排序
2. 在合并过程中，当 $b[i] \leq b[j]$ 时统计数量
3. 递归统计左右子问题的答案

时间复杂度：$O(N \log N)$

解法3：平衡树

思路：

• 使用平衡树（如C++的multiset）动态维护已处理的 $b$ 值
• 对于每个新值 $b[j]$，查询树中小于等于 $b[j]$ 的元素个数
• 将 $b[j]$ 插入平衡树

时间复杂度：$O(N \log N)$

算法细节

离散化处理

由于 $1 \leq a_i, P \leq 10^9$，$1 \leq N \leq 10^6$：

• $b[i]$ 的范围可能达到 $10^{15}$ 级别
• 必须离散化才能使用树状数组
• 离散化后值域变为 $[1, N+1]$

边界情况处理

• $b[0] = 0$：必须包含，对应空前缀
• 重复值：多个 $b[i]$ 可能相等，需要正确处理
• 整数溢出：计算 $P \cdot i$ 时可能溢出，需要使用long long

统计公式推导

最终答案 = 所有满足 $0 \leq i < j \leq N$ 且 $b[i] \leq b[j]$ 的对数

复杂度分析

时间复杂度

• 前缀和计算：$O(N)$
• 离散化排序：$O(N \log N)$
• 树状数组操作：$O(N \log N)$
• 总复杂度：$O(N \log N)$

空间复杂度

• 存储前缀和和 $b$ 数组：$O(N)$
• 离散化数组：$O(N)$
• 树状数组：$O(N)$
• 总空间：$O(N)$

特殊情况分析

$P$ 值很大

如果 $P$ 远大于所有 $a_i$，则大部分 $b[i]$ 为负数，答案可能很小。

$P$ 值很小

如果 $P$ 很小，几乎所有子数组都满足条件，答案接近 $\frac{N(N+1)}{2}$。

所有元素相等

如果所有 $a_i = c$：

• 当 $c \geq P$ 时，所有子数组都满足条件
• 当 $c < P$ 时，没有子数组满足条件

实现考虑

数据结构选择

• 树状数组：代码简单，常数小，推荐使用
• 线段树：功能更强但代码复杂
• 归并排序：无需离散化，但代码较复杂

数据类型

• 使用64位整数避免溢出
• 最终答案可能达到 $O(N^2)$ 级别，需要用long long存储

优化技巧

• 离散化时使用vector和unique
• 树状数组大小设为离散化后的值域大小
• 注意数组下标从0还是1开始

总结

本题的核心在于将平均数问题转化为前缀和差分问题，再转化为逆序对统计问题。通过巧妙的数学转化，将原问题变为经典的顺序对计数问题，然后利用树状数组或归并排序在 $O(N \log N)$ 时间内解决。关键难点在于发现 $b[i] = sum[i] - P \cdot i$ 的构造和问题转化。